一个数二进制有多少1
2025-05-22 00:14:14
起步向前走
已认证
已认证起步向前走为您分享以下优质知识
计算一个数的二进制表示中1的个数，主要有以下两种高效方法：
一、位运算优化法（推荐）
利用 `n & （n-1）` 的特性，每次操作将最右边的1变为0，直到 `n` 变为0。这种方法的时间复杂度为O（k），其中k是二进制中1的个数。
示例代码（C++）：
```cpp
int countBits(int n) {
int count = 0;
while(n) {
n &= (n-1);
count++;
}
return count;
}
```
二、递归法（适用于教学）
通过递归分解问题，奇数时在二进制末尾多一个1，偶数时右移一位继续统计。这种方法的时间复杂度为O（log n）。
示例代码（Java）：
```java
public static int findOne(int num) {
if(num == 0) return 0;
return (num % 2 == 0) ? findOne(num/2) : (findOne(num/2) + 1);
}
```
三、其他方法
逐位判断法：
通过 `n & 1` 检查最低位是否为1，然后右移 `n` 继续判断。时间复杂度为O（32）（针对32位整数）。
转换为二进制字符串：
将数字转换为二进制字符串后统计1的个数。适用于需要直观展示的场景，但效率较低。
总结：优先使用位运算优化法，兼顾效率与简洁性；递归法适合教学理解；其他方法可根据需求选择。
