c - 小整数向量的有效比较

Question

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

向

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

我想编写一个方法compare(long v1, long v2)如果非向量主导另一个向量，则返回 0，如果第一个向量占主导地位，则返回 1，如果第二个向量占主导地位，则返回 -1。

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

编辑

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

Answer 1

可以使用位操作来执行此操作。将值隔开，使每个值占用 5 位，其中 4 位表示值，空 0 位于最重要的位置，作为一种间距位。

在每个值之间

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

要进行测试，您可以在其中一个向量中将所有间距位设置为 1，然后减去第二个向量。如果间距位下方 4 位中的值在第二个位中更大，那么它将从间距位中携带该位并在结果中将其设置为零，如果不是，那么它将保持 1（第一个值大于或等于第二个）。如果第一个向量主导第二个向量，则所有间距位在减法后都将是一个。

使用 ints 的简单演示：

#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的调用。

演示

Answer 2

好吧，在 C 中，您可能会利用矢量化来做到这一点。我认为在 4 位操作数上无法直接进行比较，因此在进行比较之前，您将不得不重新打包（无论是动态还是只是将数据保留在更合适的格式中）到 8 位。由于 10 * 8 = 80 大于 64，您将需要 128 位矢量指令。

不确定Java VM是否支持这一点，但这个问题表明JNI是答案，即从Java调用C代码。