如何计算n的二进制位数
2025-04-30 15:45:50
追梦寻缘
已认证
已认证追梦寻缘为您分享以下优质知识
要计算一个整数 `n` 的二进制位数，可以使用以下两种方法：
方法一：右移法（适用于正整数）
通过不断右移 `n` 并检查最低位是否为 `1`，直到 `n` 变为 `0`，统计右移次数即为二进制位数。
```cpp
int countBits(unsigned int n) {
int count = 0;
while (n >
0) {
count += n & 1; // 检查最低位是否为1
n >
>
= 1; // 右移一位
}
return count;
}
```
方法二：位操作优化法（适用于正整数）
利用 `n & -n` 可以快速获取 `n` 的最低位 `1` 的位置（即最低位的 `1` 所在的位数），通过不断减去最低位的 `1` 并计数，直到 `n` 变为 `0`。
```cpp
int countBits(unsigned int n) {
int count = 0;
while (n >
0) {
n &= (n - 1); // 清除最低位的1
count++; // 计数
}
return count;
}
```
示例
以 `n = 29`（二进制为 `11101`）为例：
1. `29 & -29` 得到最低位的 `1` 在第 4 位（从0开始计数）；
2. `29 - 1` 得到 `28`，最低位的 `1` 在第 3 位；
3. 重复上述操作，直到 `n` 变为 `0`，统计次数为 `4`。
注意事项
上述方法仅适用于非负整数。如果 `n` 可能为负数，需要先将其转换为无符号整数（如 `unsigned int`）再处理。
对于32位整数，若 `n` 为 `0`，上述方法会返回 `0`，这是正确的。
通过这两种方法，可以高效地计算出整数的二进制位数。
