By Gee

Updated:

Contents

* 如何判断一个数里面有几个1？

Java里有个方法“Integer.bitCount(int x)”可以计算出一个数二进制里1的个数

1
2
3
4
5
6
7
8
9
public static int bitCount(int i) {
      // HD, Figure 5-2
      i = i - ((i >>> 1) & 0x55555555);
      i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
      i = (i + (i >>> 4)) & 0x0f0f0f0f;
      i = i + (i >>> 8);
      i = i + (i >>> 16);
      return i & 0x3f;
  }

感觉很神奇的样子。。。为啥是这样的呢？

先自己实现一个计算1的方法

1
2
3
4
5
6
7
8
int bitCount(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

可以看出，当n较小的时候，n>>1过几次后就变成0了。
因此可以改为：（但是速度不会变快哦）

1
2
3
4
5
6
7
8
int bitCount(int n) {
    int count = 0;
    while(n != 0){
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Contents