计算二进制 `int` 变量中 `1` 的个数,可以采用多种方法。以下是主要思路及实现方式:
一、方法一:逐位检查法(时间复杂度 O(32))
通过逐位与 `1` 进行按位与运算,统计 `1` 的个数。适用于所有 `int` 类型(包括负数)。
示例代码(Java):
```java
public static int countones(int n) {
int count = 0;
while (n != 0) {
count += (n & 1); // 检查最低位是否为1
n >>= 1; // 右移一位
}
return count;
}
```
二、方法二:位操作优化法(时间复杂度 O(k),k 为二进制中 `1` 的个数)
通过 `n &= n - 1` 操作快速消除最低位的 `1`,仅统计 `1` 的个数,效率与 `1` 的数量相关。
示例代码(Java):
```java
public static int countones(int n) {
int count = 0;
while (n != 0) {
n &= n - 1; // 清除最低位的1
count++;
}
return count;
}
```
三、方法三:处理负数(使用 `unsigned int`)
对于 `INT_MIN`(-2147483648),直接按位操作会导致溢出,需先转换为 `unsigned int` 处理。
示例代码(Java):
```java
public static int countones(int n) {
unsigned int unsignedN = n < 0 ? ~n + 1 : n; // 转换为无符号数
int count = 0;
while (unsignedN != 0) {
count += (unsignedN & 1);
unsignedN >>= 1;
}
return count;
}
```
四、其他语言实现
C++:使用 `n &= n - 1` 或逐位检查法。
Python:利用 `bin(n).count('1')` 或位操作。
总结
推荐方法:优先使用位操作优化法(方法二),效率最高且适用于所有 `int` 类型。
注意事项:处理负数时需转换为无符号数,避免溢出。