二进制数中1的个数是否为奇数

2022-10-12 760 words 2 minutes

Contents

CSAPP第二章家庭作业2.65

1
2
3


/*Return 1 when x contains an odd number of 1s; 0 otherwise.
Assume w=32 */
int odd_ones(unsigned x)

函数应该遵循位级整数编码规则,你的代码最多只能包含12个算术运算,位运算和逻辑运算.

代码

先上个代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int odd_ones(unsigned x)
{
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
    //http://stackoverflow.com/a/9133406
}

在使用循环的情况下就可以不用预先知道int的位数是多少,如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int odd_ones(unsigned x) 
{ 
	int w = sizeof(x) * 8;//获得x有多少位二进制位,这里是32 
	int n = 1; 
	while(n < w)
	{ 
		x ^= (x >> n); 
		n <<= 1; 
	} 
	return x & 1; 
	}

原理

由于异或的性质, 可以反映异或对应位上1的个数.

例:

0 ^ 0 = 0,
0 ^ 1 = 1, 
1 ^ 1 = 0.

即只有两位中有奇数个(1个)1的时候, 该位的异或值为1.也就是我们用异或结果的一个位压缩了进行异或的两位的1的个数.

依照这个思想我们可以先写出一个简单的版本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int odd_ones(unsigned x)
{ 
	unsigned s = x >> 1;
	while(x)
	{
		x ^= s;
		s >>= 1;
	} 
	return x & 1; 
}

我们设最右侧一位为第0位,最左侧一位为第w位,

即x第0位一开始代表第0位的1是否为奇数个,一次异或后变为第0和第1位的1是否位奇数个, 然后是第0~2位中的1是否为奇数个…

经过w-1次移位, 第0位代表第0~w-1位的1总共是否为奇数个, 此时返回x&1即可.

但我们发现这样移位一次只利用了每次第0位的异或结果, 有优化空间. 我们可以同时利用多个异或结果, 并且这些异或结果所代表的位不能重叠.(因为最后需要有一位代表0~w-1位中1的个数, 若有重叠就会导致某一位多计算一次). 那么最大化且不重叠的利用办法就是一次右移一半, 像将这个数字"对折"一样. 此时的异或结果中0~w/2-1位中每一位分别代表第i位和第i+w/2-1位中1的个数是否为奇数. 每次右移一半直到只剩一位, 我们只需进行$log_2w$次异或和右移运算.代码见开头.