如何统计二进制数
2025-04-30 23:15:36
朱老师
已认证
已认证朱老师为您分享以下优质知识
统计二进制数中1的个数是计算机科学中的常见问题，以下是几种常见的方法：
一、位运算法（高效方法）
通过位运算可以显著提高效率，具体方法如下：
与操作法
利用 `n & （n - 1）` 将最右侧的1变为0，每执行一次操作，计数器加1，直到 `n` 变为0。
```python
def count_ones(n):
count = 0
while n:
n &= n - 1
count += 1
return count
```
右移法
通过右移操作 `n >
>
= 1` 和按位与操作 `n & 1` 结合使用，每次检查最低位是否为1，然后右移一位继续检查。
```python
def count_ones(n):
count = 0
while n:
count += n & 1
n >
>
= 1
return count
```
二、遍历法（简单直观）
逐位检查二进制表示，从最低位到最高位，统计1的个数。
```python
def count_ones(n):
count = 0
while n:
count += n & 1
n >
>
= 1
return count
```
三、数学法（效率较低）
通过不断除以2并统计余数，从下往上构建二进制表示，再统计1的个数。
```python
def count_ones(n):
count = 0
while n:
count += n % 2
n //= 2
return count
```
四、其他方法
字符串转换法
将数字转换为二进制字符串，统计字符'1'的个数。
```python
def count_ones(n):
return bin(n)[2:].count('1')
```
查表法
预先计算0-255的1的个数，通过查表加速计算（适用于固定范围）。
性能对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|------------|------------|------------|------------------------|
| 位运算法 | O（k） | O（1） | 需要频繁统计1的个数 |
| 遍历法 | O（k） | O（1） | 简单场景 |
| 数学法 | O（log n） | O（1） | 不适合频繁调用 |
| 字符串转换法| O（k） | O（k） | 临时需要二进制表示 |
示例
以数字 `4523` 为例（二进制 `1000110101011`）：
位运算法：
通过 `n & （n - 1）` 13次操作统计1的个数；
右移法：逐位检查最低位1的个数。
推荐使用位运算法或右移法，前者在大多数情况下更高效。
