小整数向量的有效比较

Question

我有小矢量.它们中的每一个都由10个整数组成,这些整数介于0和15之间.这意味着矢量中的每个元素都可以使用4位写入.因此,我可以连接我的向量元素并将整个向量存储在单个long类型中(在C,C++,java ...中)

如果对于0,...,9,v1 [i]> = v2 [i]中的每个i,向量v1支配向量v2

我想写一个方法compare(long v1, long v2),如果非向量支配另一个,则返回0,如果第一个占优势,则返回1,如果第二个占优势,则返回-1.

除了获得每个i组件并进行正常整数比较的10倍之外,还有任何有效的方法来实现比较吗？

编辑

如果v1与v2完全相同则返回1或-1都很好

Answer 1

使用位操作可以做到这一点.将值除去,使每个值占用5位,值为4位,最高位置为空0作为一种间隔位.

在每个值之间放置一个间隔位会停止借用/携带在相邻值之间传播,这意味着您只需使用常规整数加法或减法就可以对向量执行某些类似SIMD的算术运算.我们可以使用减法来进行矢量比较.

要进行测试,可以在其中一个向量中将所有间距位设置为1,然后减去第二个.如果间隔位下面的4位中的值在第二位中更大,则它将从间隔位携带该位并在结果中将其设置为零,否则它将保持为1(第一个值更大)大于或等于第二个).如果第一个矢量在第二个矢量中占主导地位,那么在减法之后所有间隔位将是1.

使用int进行简单演示:

#define SPACING_BITS ((1<<4)|(1<<9)|(1<<14)|(1<<19))
int createVector(int v0, int v1, int v2, int v3)
{
    return v0 | (v1 << 5) | (v2 << 10) | (v3 << 15);
}

int vectorDominates(int vectorA, int vectorB)
{
     // returns 1 if vectorA dominates vectorB:
     return (((vectorA | SPACING_BITS) - vectorB) & SPACING_BITS) == SPACING_BITS;
}

int compare(int vectorA, int vectorB)
{
    if(vectorDominates(vectorA, vectorB))
        return 1;
    else if(vectorDominates(vectorB, vectorA))
        return -1;
    return 0;
}

您可以将其扩展为使用50位来使用64位值来存储10个值.您还可以vectorDominates在比较函数中内联调用.

演示