要计算一个整数转换为二进制后1的个数,可以采用以下几种方法:
一、逐位检查法
通过右移操作与1进行与运算,判断最低位是否为1,然后右移一位继续判断,直到数字变为0。
```cpp
int countones(int n) {
int count = 0;
while (n) {
count += n & 1; // 判断最低位是否为1
n >>= 1;// 右移一位
}
return count;
}
```
注意:此方法对负数处理正确,因为Java中整数采用补码表示。
二、分治法(Brian Kernighan算法)
每次将整数减1,然后与原数进行与运算,可以将最右边的1及其后面的0全部置为1,重复此过程直到n变为0。
```cpp
int countones(int n) {
int count = 0;
while (n) {
n &= (n - 1); // 将最右边的1置为0,同时将后面的0变为1
count++;
}
return count;
}
```
优点:比逐位检查法效率更高,时间复杂度为O(k),其中k是二进制中1的个数。
三、位掩码法
通过不断左移1并与原数进行与运算,统计1的个数。
```cpp
int countones(int n) {
int count = 0;
while (n) {
count += n & 1;
n <<= 1;
}
return count;
}
```
四、处理负数的情况
上述方法对负数处理正确,因为Java使用补码表示法,`n & 1`和`n - 1`操作不会改变符号位。
示例
以整数13(二进制1101)为例:
逐位检查法:
右移判断最低位是否为1,共需4次操作,结果为3。
分治法:
通过减1操作,将1101变为1100(1次操作),1100变为1011(1次),1011变为1010(1次),1010变为1001(1次),1001变为1000(1次),共5次操作,结果为3。
位掩码法:
与逐位检查法类似,结果为3。
总结
时间复杂度:O(k),其中k是二进制中1的个数。
空间复杂度:O(1)。
适用场景:适用于需要高效计算1的个数的场景,如位运算竞赛或底层系统开发。