原题链接

题目描述：
输入一个整数，输出该数二进制表示中 1 的个数。

解：

n&(n-1)

该位运算去除 n 的位级表示中最低的那一位。
（如下公式，一个二进制 -1 与 会将最后一位抹去，开始看到这个操作一脸懵逼，细想一下拍案）

  1. n       : 10110100
  2. n-1     : 10110011
  3. n&(n-1) : 10110000

时间复杂度：O(M)，其中 M 表示 1 的个数。

public int NumberOf1(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}

bitCount

java 1.8 源码中的方法 Integer.bitCount()

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;
}