欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指 - 二进制中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;
}