位奇偶校验 - 在一个整数中查找奇数个位

Question

位奇偶校验 - 在一个整数中查找奇数个位

3

我需要创建一个函数bitParity（int x），它接受一个整数并在x的二进制形式中有奇数个0时返回1，否则返回0。

例如：bitParity（5）= 0，bitParity（7）= 1 然而，这很困难，因为我只能在这个问题上使用位运算符（！〜＆ˆ| + << >> 是唯一合法的运算符）。这意味着不能使用循环，if-then或类似的东西。可以使用常量。

到目前为止，我的方法行不通，但我想应该将整数的位移16次，8次和4次，并XOR剩余的整数。

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

- Dennis

3

你应该经常去这里查找位运算的例子：http://graphics.stanford.edu/~seander/bithacks.html#ParityLookupTable <- 把它加入书签。然而，你应该自己努力尝试并发布你所做的内容。由于这是作业，你应该确保充分理解正在发生的事情，而不仅仅是从该链接中复制和粘贴代码。 - Joe

查找表是最好的方法。256字节的存储空间是很小的代价。如果您正在使用32位整数，只需从表中读取4次即可。 - BitBank

1

除了@Joe提到的内容，您还可以参考http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know。这里有一些我认为很有用的原始位操作技巧。 - Sangeeth Saravanaraj

1

请查看此链接 https://dev59.com/FGEi5IYBdhLWcg3wIJJH#21618038 - tf3

3个回答

6

这个问题可以通过循环来解决。但是这里有一种不需要循环的方法。

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)

Edit: I don't need the &. A better version:

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

- Kendall Frey

非常感谢！我已经非常接近了，只是漏掉了最后的x&1。你能给我一点见解，说明你是如何得出这个结论的吗？谢谢。 - Dennis

我不确定。我在思考这个问题，突然有了一个灵感。我最初的想法是逐位进行异或运算。但那样会很丑陋。我现在将其视为将数字反复折叠到自身的方式。 - Kendall Frey

0

这是我在撰写学士论文期间使用的一个函数；）

/** 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）可以分为两个每个4b长的部分，这意味着有16个值是容易存储和重复使用的。因此，您从整数中取出前8b，将它们分成两个部分。确保它们都在区间<0,15>内，并直接获取位计数。重复这个过程：）

- Vyktor

请查看约束条件。 - Keerthana Gopalakrishnan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rudu · Accepted Answer

对于32位数字：

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

Note* 0x6996 代表数字1、2、4、7、8、11、13和14的位向量。这些位向量可以表示为奇数位的所有四位值。在0x6996中，如果该位在向量中对应于（1、2、4、7、8、11、13或14），则设置了一个位。因此，在移位x之后，(0x6996 >> x) & 1就有意义了。如果x等于位向量中的任何值，则此表达式将仅返回1，这意味着已设置奇数位。