二进制数中有多少个1
2025-05-09 12:52:18
星海幻梦
已认证
已认证星海幻梦为您分享以下优质知识
要计算一个二进制数中1的个数，可以使用位运算来高效实现。以下是几种常见的方法：
一、使用 `n & （n-1）` 方法
原理：
每次将二进制数最右边的1变为0，其余0变为1，重复此操作直到数变为0，统计操作次数。
示例：
对于二进制数 `10001100`：
- `10001100 - 1 = 10001011`（最右边的1变为0）
- `10001011 - 1 = 10001010`（下一个1变为0）
- 重复操作直到结果为0，统计次数。
二、使用异或运算
原理：
通过异或运算的性质 `a ^ b ^ c = a ^ （b ^ c）`，可以逐位判断1的个数。
实现：
不断与 `0x55555555`（二进制为 `01010101010101010101010101010101`）进行异或操作，每进行一次异或，最右边的1会变为0，统计操作次数。
三、逐位检查法
原理：
通过 `n & 1` 判断最低位是否为1，然后右移一位继续判断。
示例：
对于二进制数 `1100`：
- `1100 & 1 = 0`（最低位为0）
- `1100 >
>
1 = 110`，`110 & 1 = 0`
- `110 >
>
1 = 11`，`11 & 1 = 1`
- `11 >
>
1 = 1`，`1 & 1 = 1`
- `1 >
>
1 = 0`（结束循环），统计次数。
四、处理负数
补码表示：负数在计算机中以补码形式存储，最高位为符号位。上述方法同样适用，因为补码本质是二进制加1的结果。
五、示例代码（Python）
```python
def count_ones(n):
count = 0
while n:
n &= n - 1 消去最右边的1
count += 1
return count
测试
print(count_ones(13)) 1101，输出2
print(count_ones(-5)) 补码为11111111111111111111111111110101，输出32
```
总结
时间复杂度：`O（k）`，其中 `k` 是二进制数中1的个数。
空间复杂度：`O（1）`，仅使用常数空间。
适用场景：适用于需要高效计算1的个数的场景，如位图处理、加密算法等。
