计算二进制int变量有多少1
2025-05-09 17:27:04
星海幻梦
已认证
已认证星海幻梦为您分享以下优质知识
计算二进制 `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` 类型。
注意事项：处理负数时需转换为无符号数，避免溢出。
