如何统计数字中二进制中的1的个数

如何统计数字中二进制中的1的个数

直接进行位移是不好的，比较浪费时间，在严格环境中会超时。

一种改进的思路是在循环中判断n = n&(n-1)可以减少时间

一个数字5

0101

减去1就是

0100

就是自动去掉最右边一位二进制1

知道这个原理进而进行统计进行了多少次相减即可，注意整个运算是按照补码进行运算的。

#include<iostream>
using namespace std;

int main() {
	unsigned int ans=0,n;
	cin>>n;
	while(n) {
		n=n&(n-1);
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}

计算机计算是通过将原码转换为反码再转换为补码而进行计算的。

此时（以8位宽为例）

-1

原码：1000 0001

反码：1111 1110

补码：1111 1111

此时上述的求解方法将会得到结果：8，我的计算机使用int定义则得到结果32.

如果你需要求的计算机补码的二进制1的位数，即可了，如果需要求的是原码的二进制位数，那么还要进行如下处理：

#include<iostream>
using namespace std;

int main() {
	int ans=0,n;
	cin>>n;
	if(n<=0) {
		n=(-n);
		//看你需不需要将符号位记作一个二进制，需要则ans=1,不需要则为0
		ans=1;
	}
	while(n) {
		n=n&(n-1);
		ans++;
	}
	cout<<ans<<endl;
	return 0;
}