整数的二进制表示中1的个数

1、循环方法

下面介绍另外一种方式，可以通过比上述少的比较次数来统计出数的二进制表示中1的个数。

首先作如下分析：

       n & (n - 1)可以将n的二进制表示中最右侧的一个1去掉，例如1100 减去1得到1011，那么 1100 & 1011得到1000，即将1100最右侧的一个1去掉。如下函数每次循环就去掉其二进制表示中一个1，那么函数循环的次数就是其二进制表示中所含1的个数。

int count_one_bits3(int value) {
	int count = 0;
	while (value) {
		++count;
		value = value & (value - 1);
		//int v1 = value;
		//cout << value << " ";
	}
	cout << endl;
	return count;
}

while循环结束的条件是value为0，也就是当value是2的n次幂时，下一次循环就结束了，因为2的n次幂的二进制表示中仅含有一个1。循环中value = value & (value - 1)使得每次循环后，value的二进制表示中1的个数少一个。该方法与前两个方法比，循环的次数少。

如下图，输入value为8888，可以看出方法1执行while循环14次，方法3执行while循环6次。方法3每次循环后value的二进制中1的个数少一个。

2、位移方法

参考文章：二进制位的翻转和二进制表示中1的个数