二进制数有多少个1
2025-05-03 13:23:56
智启星辰
已认证
已认证智启星辰为您分享以下优质知识
根据您的问题，二进制中1的个数计算方法可分为以下两种情况：
一、单个整数的二进制1的个数
基本思路
通过位运算逐位检查整数的二进制表示，统计1的个数。具体步骤为：
- 使用无符号右移操作（`n & 1`）判断最低位是否为1，是则计数器加1；
- 将整数右移一位，重复上述过程直到整数变为0。
处理负数
负数在计算机中以补码形式存储，需先将其转换为无符号数再统计1的个数，避免符号位影响结果。
示例代码
```cpp
int NumberOf1(int n) {
unsigned int nu = n;
int num = 0;
while(nu) {
num += nu & 1;
nu >
>
= 1;
}
return num;
}
```
二、1到n所有整数的二进制1的个数
分治法
利用二进制位特性，统计每个位上1出现的次数。例如：
- 对于第k位（0开始计数），每2^k个数中，该位为1的次数为2^（k-1）；
- 若n大于2^k-1，则该位1的次数为2^k，否则为n % 2^k。
时间复杂度
该算法的时间复杂度为O（32），因为32位整数的每一位最多被统计一次。
示例
输入n=4，二进制1的分布为：
- 1: 001 → 1个1
- 2: 010 → 1个1
- 3: 011 → 2个1
- 4: 100 → 1个1
总计5个1。
总结
单个整数：
使用位运算高效统计，需注意负数处理；
1到n所有整数：通过分治法统计，时间复杂度为O（32）。
