n的二进制表示的1个数是多少
2025-05-10 12:05:22
肖老师
已认证
已认证肖老师为您分享以下优质知识
要计算一个整数 `n` 的二进制表示中 `1` 的个数，可以采用以下几种方法：
一、逐位检查法（最基础方法）
通过循环检查每一位是否为 `1`，时间复杂度为 O（k），其中 `k` 是 `n` 的二进制位数（对于 32 位整数，最多 32 次循环）。
```c
int BitCount(unsigned int n) {
int count = 0;
while (n >
0) {
count += n & 1; // 检查最低位是否为1
n >
>
= 1; // 右移一位
}
return count;
}
```
二、位操作优化法
n & （n - 1） 方法
该方法的原理是每次将 `n` 的最右边的 `1` 变为 `0`，同时将该位右边的所有 `0` 变为 `1`，直到 `n` 变为 `0`。每执行一次操作，`n` 的二进制表示中 `1` 的个数减少 `1`。时间复杂度为 O（m），其中 `m` 是 `n` 的二进制表示中 `1` 的个数。
```c
int Countones(unsigned int n) {
int count = 0;
while (n) {
n &= (n - 1); // 移除最右边的1
count++; // 计数器加1
}
return count;
}
```
分治法（递归）
利用奇偶性递归计算：若 `n` 为奇数，则 `1` 的个数为 `n/2` 的二进制表示中 `1` 的个数加 `1`；若 `n` 为偶数，则 `1` 的个数等于 `n/2` 的二进制表示中 `1` 的个数。
```c
// 递归版本
int CountonesRecursive(unsigned int n) {
if (n == 0) return 0;
if (n % 2 == 1) return 1 + CountonesRecursive(n / 2);
else return CountonesRecursive(n / 2);
}
// 迭代版本
int CountonesIterative(unsigned int n) {
int count = 0;
while (n) {
count += n % 2; // 统计最低位
n >
>
= 1; // 右移
}
return count;
}
```
三、预处理表法（适用于范围查询）
如果需要计算从 `1` 到 `n` 的所有整数的二进制表示中 `1` 的总数，可以预先计算 `0` 到 `2^k - 1` 范围内每个数的 `1` 的个数，然后利用规律递推计算。时间复杂度为 O（k^2），其中 `k` 是 `log2（n）`。
```c
include
include
define MAXK 32 // 32位整数最大k值
int precomputeones(int k) {
int *ones = (int *)calloc(k, sizeof(int));
for (int i = 0; i < k; i++) {
ones[i] = i == 0 ? 0 : ones[i / 2] + 1;
}
return ones;
}
int CountonesRange(unsigned int n) {
int k = 0;
while (n >
0) {
k++;
n >
>
= 1;
}
int *ones = precomputeones(k);
int count = 0;
for (unsigned int i = 1; i
