不使用循环计算32位整数的奇偶校验位//bitParity-returns1ifxcontainsanoddnumberof0's“返回1假如x里有基数的0”*Examples:bitParity(5)=0,bitParity(7)=1*Legalops:&^|+>可以使用的符号x=(x>>16)^

Question

不使用循环计算32位整数的奇偶校验位
//bitParity - returns 1 if x contains an odd number of 0's “返回1假如x里有基数的0”
* Examples:bitParity(5) = 0,bitParity(7) = 1
* Legal ops:& ^ | + > 可以使用的符号
x = ( x >> 16 ) ^ x;
x = ( x >> 8 ) ^ x;
x = ( x >> 4 ) ^ x;
x = ( x >> 2 ) ^ x;
x = ( x >> 1) ^ x;
return (x & 1);
}
完全看不懂,我对bit的了解太模糊了,越基础越好,越详细越好,为什么要移位,这个方法的原理是什么?而且我带进去得出来的答案和问的相反.

Answer 1

理解这段代码的要点在于搞明白三个操作符：
移位>>：向右移动指定的位数,最右边挤掉相应的位数会被丢弃,而左边补0；
按位异或^：两个数按位进行异或运算,若对应的两位不同（即一个为0,另一个为1）,返回1；否则（即同为0或同为1）返回0.
按位与&：两个整数按位进行与运算,例如 x&1得到的结果是取出x的最右一位.
 
明白了这两个操作符,后面就容易理解了：
x = ( x >> 16 ) ^ x; 这一句把高16位右移16位,和低16位进行按位异或运算,这样就会消掉偶数个数的1（两个相同位置的1会得到0）.需要注意的是,计算是按照32位整数进行的,但是高16位的结果我们并不关心,因为原整数究竟有奇数或是偶数个1的信息已经完全反映在低16位里面了.
x = ( x >> 8 ) ^ x; 这一句进一步把低16位里面的左边8位右移并与右边8位进行异或运算.类似的,运算仍然是按照32位整数进行的,但是我们只关心最右边的8位,经过这一步运算后,又会消掉偶数个1.
x = ( x >> 4 ) ^ x; 后面依此类推.
x = ( x >> 2 ) ^ x;
x = ( x >> 1) ^ x; 直到这一步,我们把原32位整数包含1的个数奇偶性信息最终体现在最右边的1位上面.
return (x & 1); 通过按位与运算,把最后一位取出并返回.
就整个算法而言,你可以这样来理把32位整数折叠成为两个16位整数进行运算,各对应bit若同为1则结果为0,有一个为1则结果为1,同为0结果也为0,所以折叠的结果会消除偶数个1,不改变奇偶性信息.然后再折叠得到8位数、4位数、2位数,最后得到的1位数就是奇偶校验位了.
 
哦对了,题目说的是“奇数个0”,这个和“奇数个1”是一样的,原因不用解释了吧?