当x中包含偶数个1返回1，否则返回0

题目描述：

int even_ones(unsigned x);

函数应该遵循位级整数编码规则，不过你可以假设数据类型int 有w=32位。

你的代码最多只能包含12个算术运算、位运算和逻辑运算。

代码如下：

bool OddOnes(int x)  
{  
    x = x ^ (x >> 1);  
    x = x ^ (x >> 2);  
    x = x ^ (x >> 4);  
    x = x ^ (x >> 8);  
    x = x ^ (x >> 16);  
    return !(x & 1);  
} 
           

分析：

我在这里引用网友Matrix67的部分分析：

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

00000000000101000000111011011000

XOR 0000000000010100000011101101100

---------------------------------------

00000000000111100000100110110100

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

00000000000111100000100110110100

XOR 000000000001111000001001101101

---------------------------------------

00000000000110011000101111011001

结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。

相信很多网友还是没有看明白怎么回事，其实以上部分的形式化表示如下：

加上X的表示为x31....x0则：

第一次异或：x = x ^ (x >> 1);

x:

x>>1：

x ^ (x >> 1):

第二次异或：x = x ^ (x >> 2);

x:

x >> 2:

x ^ (x >> 2):

第三次异或：x ^ (x >> 4)

x:

x >> 4:

x ^ (x >> 4):

第四次异或：x = x ^ (x >> 8)

x:

x >> 4:

x ^ (x >> 4):

第五次异或：x = x ^ (x >> 16)

x:

x >> 16:

x ^ (x >> 16)

从以上过程可以看出：在经过了五次异或之后，最后一位二进制值确实表示了整个二进制字符串中1出现个数的奇偶性。

参考博客：http://www.matrix67.com/blog/archives/264