位级运算之计算整数位级表示奇偶性

位级运算之计算整数位级表示奇偶性

Author：Once day Date：2022年7月31日

漫漫长路刚刚开始，不要甘于平凡。

本算法基于C语言环境。

1.引言

可以只依靠基本的位级运算来计算位级表示的奇偶性。

如一个含有w位的向量 $b_{n-1}b{n}_{n-2}\cdot \cdot \cdot \cdot \cdot \cdot b_1{b}_0$。

如果其中有奇数个位为1，那么返回值1，否则返回0。

如，[0001]返回1，[0011]返回0。

那么存在一种对数增长度的算法，来计算其值，而且无需判断语句。

2.实现

最简单的实现方式就是依次判断每位是否为1，然后累积起来，判断是否为奇数个。这样效率太低。

可以依靠异或运算加速判断。

这里假设w=8位：

对于形如[01010111]的位级表示，其有奇数个1，所以应该返回1。

异或运算规律如下：

因此，将[01010111]拆成两半，即[0101]和[0111]，然后异或0101b ^ 0111b = 0010b，如果有一对1，那么该位异或结果为0，如果有一个1，那么结果为1。

对于[0010]，则可以拆分成[00]和[10]，按此规律继续异或，最终将为1。

根据配对规则，如果有奇数个1，那么最后异或一定剩下1，该算法是递归的，其复杂度为$lo{g}_{2}w$。

可表示为：

unsigned x; //假设32位
x=x^(x>>16);
x=x^(x>>8);
x=x^(x>>4);
x=x^(x>>2);
x=x^(x>>1);
1
2
3
4
5
6

---

---

完…