algorithm - 检查是否设置了奇数位的快速方法？

Question

我需要确定在某种类型的变量中设置的位数（可能是 32 位无符号或 64 位无符号）是否为奇数。我读了：

如何计算 32 位整数中设置的位数？

这当然非常有用，但我想做得更好，因为我只需要一个二进制答案，而不是整个计数。我想替换一字节或两字节的 LUT 应该很快，但也许可以以某种方式改进非 LUT 代码。

Answer 1

异或所有位。要做到最佳，您可以通过将 32 MSB 与 32 LSB 进行异或运算，将 64 位数减少到 32 位数。然后将 32 位数减少到 16 位数，最后将 16 位数减少到 8。一旦有了一个字节，就可以使用一个简单的映射表来确定您有偶数位数还是奇数位数。

Answer 2

纯位解决方案：反复异或您的值的下半部分和上半部分，如下所示：

function IsOdd(n)
{
    n ^= n >> 32;
    n ^= n >> 16;
    n ^= n >> 8;
    n ^= n >> 4;
    n ^= n >> 2;
    n ^= n >> 1;
    return (n & 1) == 1;
}

这可以使用预先填充的查找表进行优化：

function Prepopulate()
{
    bool[] answer = new bool[256];
    answer[0] = false;
    for (int i = 1; i < 256; i++)
        answer[i] = answer[i >> 1] ^ ((i & 1) == 1);
}
function IsOdd(n)
{
    n ^= n >> 32;
    n ^= n >> 16;
    n ^= n >> 8;
    return answer[n & 255];
}

您可能希望使用不同的预填充表格大小；在我的示例中，我使用了一个 8 位表（256 个项目）。

Answer 3

对于现代处理器和 gcc 编译器：

 IsOdd = __builtin_popcount(value)&1;

或者，正如 Falk 指出的那样，简单地说：

 IsOdd = __builtin_parity(value);

gcc 内置文档在这里。