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

Question

我需要确定某个类型的变量(可能是32位无符号或64位无符号)中设置的位数是否为奇数.我读了:

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

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

Answer 1

XOR所有位.为了达到最佳效果,您可以通过将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 个项目）。