判断二进制数中的1有奇数个还是偶数个 - 计算机的艺术 - 博客频道 - CSDN.NET

判断二进制数中的1有奇数个还是偶数个 - 计算机的艺术 - 博客频道 - CSDN.NET
http://www.matrix67.com/blog/archives/266
判断（32位）整数的二进制表示中的1有奇数个还是偶数个

第一次异或的结果，第i个位置上是1代表原数中第i位和第i+1位有一个为1，也就是奇数个1。也就是说，某个位为1，代表从它开始向左连续两位中1的个数是奇数（异或的本质）。
第二次异或，注意是两位两位的比较了，所有x是和x>>2做异或运算，比如，若结果第6位为1，那么代表上一次的结果的第6位和第8位有奇数个1，也就是原数中第6,7,8,9位中有奇数个1。
同样，到第五次运算结束后，过第0位为1代表0到31位共奇数个1。
整个过程就是不断的压缩信息，先用1位代表从本位开始向左的2位中1的奇偶，然后向左的4位，向左的8位。。。。

二进制运算是很强大的，平时应多注意思考和总结，恰当的使用二进制运算可以大大提高程序的效率。

最直接的思路就是求二进制数中1的个数，然后确定是偶数还是奇数。

1. bool OddOnes(int x)   
2. {  
3.     int cnt = 0;  
4.     while(x)  
5.     {  
6.         cnt++;  
7.         x &= x-1;  
8.     }  
9.     return cnt & 1;  
10. }  

先求x二进制中1的个数，方法就是通过x&= x-1去掉最右端的1，直到x变为0，去掉了几次1就是原x二进制中含有多少个1；然后确定个数为奇数还是偶数。

为了说明上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如下：

    00000000000101000000111011011000
X   0000000000010100000011101101100
—————————————
    00000000000111100000100110110100

    得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：

     00000000000111100000100110110100
X      000000000001111000001001101101
—————————————
    00000000000110011000101111011001

    结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。
http://blog.csdn.net/pinghegood/article/details/8194681
Read full article from 判断二进制数中的1有奇数个还是偶数个 - 计算机的艺术 - 博客频道 - CSDN.NET