二进制表式中有多少个 1.
in 算法 with 0 comment

二进制表式中有多少个 1.

in 算法 with 0 comment

计算在一个 32 位的整数的二进制表式中有多少个 1.

样例

给定32(100000),返回1

给定5(101),返回2

给定1023(111111111),返回9

方法一 普通法

最容易想到的方法,通过移位加计数,一个个计算统计1的个数

public int countOnes1(int num){
    int count = 0;
    while(num!=0){
        if(num%2==1)
            count++;
        num=num/2;
    }
    return count;
}

改进的普通法

用位操作替代方法一

public int countOnes2(int num){
    int count = 0;
    while(num!=0){
        count +=num&0x01;
        num = num>>1;
    }
    return count;
}

方法三 快速法

这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1,同时累加计数器,直至n为0
为什么n &= (n – 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,8(1000)= 7(0111)+ 1(0001),所以8 & 7 = (1000)&(0111)= 0(0000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如7(0111)= 6(0110)+ 1(0001),所以7 & 6 = (0111)&(0110)= 6(0110),清除了7的二进制表示中最右边的1(也就是最低位的1)

public int countOnes3(int num){
    int count = 0;
    while(num!=0){
        num = num & (num-1);
        count++;
    }
    return count;
}
Responses