剑指 - 二进制中1的个数
程序员文章站
2024-03-17 13:03:46
...
题目:请实现一个函数,输入一个整数,输出该数二进制的表示中1的个数。例如把9表示成二进制是1001,有2位1。
思路1:
先判断整数二进制表示中最右边以为是不是1,接着把输入的整数右移一位,此时原来的倒数第二位变成的最后一位,再判断是不是1,这样每此移动一位,直到整个整数都变成0为止,其中判断是否是1可以将整数与1做与运算,若结果是1表示该整数的二进制表示最右边一位是1,否则是0。
public int bitCount2(int x) {
int count = 0;
while (x != 0) {
count += x & 1;
x = x >> 1;
}
return count;
}
此外,向右位移一位就相当于该整数除以2,但是除法在计算机中运算效率没有位移运算快。
思路2:
前面的思路计算出整数中二进制数中1的个数,需要循环等于二进制数的位数的次数,例如:32位的整数需要循环。
那么有没有只循环二进制数中1的个数的算法呢?
答案是肯定有的,我们要清楚思路1之所以要循环这么多次是因为每次右移后都需要判断最低位是否是1,即使最低位是0还是需要判断的,那么,如果能够每循环一次就减少一个较低位的1,那么就能更迅速的得到结果。
重点:我们发现把一个整数减去1,都是把最右边的1变成0,如果它的右边还有0,所有的0都变成1,而它左边的所有位都保持不变。如果我们把一个整数和它减去1的结果做与运算,相当于把最右边的1变成0。
以1100为例,它减去1的结果是1011,再把1100与1011做与运算,得到的结果就是1000,我们把1100最右侧的1变成了0,成功的减掉了一个1位。
总结起来就是:把一个整数减去1,再和原整数做与运算,会把该整数最右边的一个1变成0,那么一个整数中的二进制表示中有多少个1,就可以进行多少次这样的操作。
public int bitCount(int x) {
int count = 0;
while (x != 0) {
x &= x - 1;
count++;
}
return count;
}