奇偶校验位code的奇数位 [英] Bit parity code for odd number of bits

问题描述

我试图找到一个位串的奇偶性，使其返回1如果x具有0的奇数＃。结果
我只能用基本的位运算和我有什么迄今为止通过大多数测试，但我想知道两件事：

1. 为什么X ^（X +〜1）工作？我偶然发现了这一点，但它似乎给你1，如果有奇数个位数，如果连别的东西。像7 ^ 6 = 1，因为7 = 0b0111




2. 这是解决问题的这个方向是正确的？我假设我的问题是从第一操作所产生的，特别是（X +〜1），因为它会溢出一定2的补数。谢谢

code：

  INT bitParity（INT X）{
    INT第一= X ^（X +〜1）;
    INT秒=第一^ 1; //如果第一XOR给了1，你会在这里返回0
    INT结果= !!第二;
返回结果;
}
 

解决方案

我会用实际计数，而不是位级别的黑客是利用数字重新presentation，这将既感到更安全，更清洁，容易明白。也许慢，当然，不过这是一个相当不错的折衷尤其是当一个人不知道的业绩预期什么。

做这一点，只写code计算1位的数目，最直接的正解通常归结为一个循环。

更新：鉴于（怪异和恼人）的限制，我的回答很可能是的开卷在给出的循环天真解决方案 bithacks 页面上。那会不会是pretty，但我可以去​​做些有用的事情。 ：）

I am trying to find the parity of a bitstring so that it returns 1 if x has an odd # of 0's.
I can only use basic bitwise operations and what I have so far passes most of the tests, but I'm wondering 2 things:

1. Why does x ^ (x + ~1) work? I stumbled upon this, but it seems to give you 1 if there are an odd number of bits and something else if even. Like 7^6 = 1 because 7 = 0b0111

2. Is this the right direction of problem solving for this? I'm assuming my problem is stemming from the first operation, specifically (x + ~1) because it would overflow certain 2's complement numbers. Thanks

Code:

int bitParity(int x) {
    int first = x ^ (x + ~1);
    int second = first ^ 1; // if first XOR gave 1 you'll return 0 here
    int result = !!second;
return result;
}

解决方案

I would use actual counting rather than bit-level hacks that exploit the representation of the numbers, that would both feel safer and be more clean and easy to understand. Probably slower, of course, but that's a quite nice trade-off especially when one doesn't know anything about the performance expectations.

Do to this, just write code to count the number of 1 bits, the most straight-forward solution generally boils down to a loop.

UPDATE: Given the (weird and annoying) limitations, my response would probably be to unwind the loop given in the "naive" solution on the bithacks page. That wouldn't be pretty, but then I could go do something useful. :)

这篇关于奇偶校验位code的奇数位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！