c - 小整数 vector 的高效比较

Question

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

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

我想写一个方法 compare(long v1, long v2) 如果没有一个 vector 支配另一个 vector ，它将返回 0，如果第一个 vector 支配则返回 1，如果第二个 vector 支配则返回 -1占主导地位。

除了获取每个 i 分量并进行 10 次正常整数比较之外，是否有任何有效的方法来实现比较？

编辑

如果 v1 与 v2 完全相同返回 1 或 -1 都可以

Answer 1

可以使用位操作来做到这一点。将您的值隔开，使每个值占用 5 位，其中 4 位用于值，最重要位置的空 0 作为一种间隔位。

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

要进行测试，您可以将其中一个 vector 中的所有间距位设置为 1，然后减去第二个 vector 。如果间隔位下面的 4 位中的值在第二个中更大，那么它将从间隔位中携带该位并在结果中将其设置为零，否则它将保持为 1(第一个值更大大于或等于第二个)。如果第一个 vector 支配第二个 vector ，则减法后所有间隔位都将为 1。

使用整数的简单演示:

#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;
}

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

Demo