计算一个二进制数中的1的个数

2017-04-26  本文已影响69人  senninha

计算一个二进制数中的1的个数

1.循环法

首先二进制数有这么一个性质,当一个数减去1再与原来的数字去&运算,得到的结果其实是将原来的那个数字的最右边的那个1变成0后的数字。
举个粒子:
10101010
10101010 - 1 = 10101001
10101010 & 10101001 =
10101000
所以执行一次这样的运算就把二进制数的一个1给消灭了。。。
运用这样的性质还可以去解决其他的移位问题
来上代码:

public static int bitNums0(int i){
        int count = 0;
        while(i != 0){
            i = (i - 1) & i;
            count++;
        }
        return count;

2. 不使用循环的方法

01010111

  1. 先把一个二进制数分为两个两个一组,01,01,01,11,
    组内的高位和低位相加,
    然后再四个分为一组,组内高二位与第二位相加
    ...以此,最后的那个就是结果。
public static int bitNums(int i){
        int bit2 = 0x55_55_55_55;//0101 0101 0101...
        int bit4 = 0x33_33_33_33;//0011 0011 0011...
        int bit8 = 0x0f_0f_0f_0f;    //0000 1111 0000 1111...
        int bit16 = 0x00_ff_00_ff;  //0000 0000 1111 1111...
        int bit32 = 0x00_00_ff_ff;  //0000 0000 0000 0000...1111 ...
        
        i = ((i >>> 1) & bit2) + (i & bit2);
        i = ((i >>> 2) & bit4) + (i & bit4);
        i = ((i >>> 4) & bit8) + (i & bit8);
        i = ((i >>> 8) & bit16) + (i & bit16);
        i = ((i >>> 16) & bit32) + (i & bit32);
        
        return i;
    }
上一篇 下一篇

猜你喜欢

热点阅读