bitParity - 查找整数中的奇数位

Question

我必须创建一个函数 bitParity(int x) ，它接受一个整数，如果中有奇数个 0 则返回 1位形式为x，否则为0。

例如： bitParity(5) = 0, bitParity(7) = 1

但是，这很困难，因为我只能在这个问题上使用位运算符 (! ∼ & ˆ | + <>> 是唯一合法的）。这意味着，没有循环、if-then 或任何类似的东西。可以使用常量。

到目前为止，我所拥有的不起作用，但我认为我应该移动整数 16、8 和 4 的位次并对剩余整数进行异或运算。

有人可以提供一些建议吗？谢谢。

Answer 1

对于 32 位数字：

function bitParity(int x) {
   x ^= x >> 16;
   x ^= x >> 8;
   x ^= x >> 4;
   x &= 0xf;
   return (0x6996 >> x) & 1;
}

注意* 0x6996 表示数字 1、2、4、7、8、11、13 和 14 的位向量。所有 4 位值都可以表示为奇数位数。在 0x6996 中，如果某个位在向量中的位置对应于 (1、2、4、7、8、11、13 或 14)，则该位被设置。

这就是为什么 (0x6996 >> x) & 1 有意义，在移位 x 后，如果 x 等于位向量中的任何值，则该表达式只会返回 1，这意味着设置了奇数个位。

Answer 2

这可以通过循环正确解决。但这里有一种方法可以做到这一点。

x = (x & 0x0000FFFF) ^ (x >> 16)
x = (x & 0x000000FF) ^ (x >> 8)
x = (x & 0x0000000F) ^ (x >> 4)
x = (x & 0x00000003) ^ (x >> 2)
x = (x & 0x00000001) ^ (x >> 1)

编辑：我不需要 &。更好的版本：

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;

Answer 3

这是我在学士论文工作期间使用的函数之一；）

/** Calculates number of bits in unsigned char
 * @brief Bit count
 * @param input to be checked
 * @return int 0-8
 */
int bitCount( unsigned char input)
{
    static unsigned char count[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
    return (int)(
            count[ input & 0x0f] +
            count[ (input >> 4) & 0x0f]
    );
}

因此 4B 整数的总计数将是：

int bytes = bitCount( (unsigned char)((number >> 0)&255))
            + bitCount( (unsigned char)((number >> 8)&255))
            + bitCount( (unsigned char)((number >> 16)&255))
            + bitCount( (unsigned char)((number >> 24)&255));

奇偶校验：

 return bytes%2;
 return bytes&1; // if you preffer

我一直想重用这些代码:)

编辑：
您可能会注意到 unsigned char (8b) 可以分为 2 部分，每部分 4b 长，这意味着 16 个值易于存储和重用。所以你从整数中取出第一个 8b，将它们分成两部分。确保它们都在<0,15>区间内，直接获取位数即可。重复 ：）