Integer.bitCount（二进制表达式中1的个数）

做LeetCode 401题时发现的，该题使用打表法，需要提前计算每个时间对应二进制中1的个数，对应到191题计算二进制表达式中1的个数。
给出一个整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）
比如数字6，转换为2进制为110，那么’1’的个数就是2。
一般有如下方法：

位数检查法

最朴素的做法，一位一位循环判断，统计1的个数。
时间复杂度O(n)，空间复杂度O(1)，n固定为32。

    public int hammingWeight(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans += ((n >> i) & 1);
        }
        return ans;
    }

右移统计法

对于位数检查法，即使 n 的高位都是 0，我们也会对此进行循环检查。
因此另外一个做法是：通过 n & 1 来统计当前 n 的最低位是否为 1，同时每次直接对 n 进行右移并高位补 0。
时间复杂度O(n)，空间复杂度O(1)，n固定为32。

    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += (n & 1);
            n >>>= 1;
        }
        return ans;
    }

短除法

每次循环消除最低位的1，有多少个1就消除多少次。
时间复杂度O(n)，空间复杂度O(1)，n固定为32。

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

lowbit法

此方法是循环做减法运算，每次去掉最低位的1。
时间复杂度O(n)，空间复杂度O(1)，n固定为32。

    public int hammingWeight(int x) {
        int ans = 0;
        // 每次减去最低位的1
         while (x != 0){
              x -= lowbit(x);
             ans++;
         }
        return ans;
    }
    public int lowbit(int x) {
        // x & -x等同于 x & (~x+1) x为奇数时结果为1，偶数时结果为最低位的1和后面的0
        return x & -x;
    }

分组统计（Integer.bitCount）

JDK源码提供了此方法用来统计二进制数中1的个数，基本思想是分组，每2位进行统计1的个数，
然后合并结果，然后得到的结果又可以继续分组合并。
时间复杂度O(log n)，空间复杂度O(1)，n固定为32。

简单原型分析

此代码为简单原型版本，不是jdk源码，代码如下:

    public int hammingWeight(int n) {
        n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
        return n;
    }

原理是每两个bit为一组，分别统计每一组有几个1，然后把结果保存到这两个bit上。
两个bit如何计算1的个数：
把两个bit拆分开，每一个bit前面进行补一个0，然后再进行相加即可
0b11: 01 + 01 = 10 = 2，
0b10: 01 + 00 = 01 = 1，
0b01: 00 + 01 = 01 = 1，
0b00: 00 + 00 = 00 = 0。
特殊值：

0x55555555    = 01010101 01010101 01010101 01010101 (偶数位为0，奇数位为1)
0x33333333    = 00110011 00110011 00110011 00110011 (1和0每隔2位交替出现)
0x0f0f0f0f    = 00001111 00001111 00001111 00001111 (1和0每隔4位交替出现)
0x00ff00ff    = 00000000 11111111 00000000 11111111 (1和0每隔8位交替出现)
0x00ff00ff    = 00000000 00000000 11111111 11111111 (1和0每隔16位交替出现)

算法实现：

1. int32位，首先分16组，每组2位
2. (n & 0x55555555)

将每一组左位的数字变成0，只保留了原来的右位，每一组bit的左位为0

1. (n >>> 1) & 0x55555555

首先右移一位进行错位，此时左位变为了右位，然后把这时的左位变为0，
相当于保留了原来的左位，每一组bit的左位为0

1. 进行相加

试着分析第一行代码：n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
假设数字n为655，二进制为10 10001111，其中1的个数是6，
n & 0x55555555：
01010101 01010101 01010101 01010101
& 00000000 00000000 00000010 10001111
101

把n右移一位（n >>> 1，去掉末尾的1），结果是00000001 01000111，
(n >>> 1) & 0x55555555：
01010101 01010101 01010101 01010101
& 00000000 00000000 00000001 01000111
1 01000101
之后错位的结果进行相加：
1 01000101
+ 101
1 01001010
这个结果我们前面进行补0，结果是01 01 00 10 10
对比原来的n，10 10001111，
结果的每2位表示了这两位中1的个数，10表示为2, 01表示为1，
对比发现完全一致，接下来也是一样的套路，刚刚是每2位进行统计合并
然后就是4位，8位，16位，一直到32位，
因为int类型就是32位的，所以最后返回结果n就可以了。

JDK源码分析

源码如下：

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

该代码比上面的原型写法效率要高，稍稍复杂一点点。

两个bit计算1的个数用的不是加法，而是减法，和上面稍有不同：
直接用这个数本身减去左位的数，如果是1就-1，是0就-0。
0b11: 11 - 01 = 10 = 2，
0b10: 10 - 01 = 01 = 1，
0b01: 01 - 00 = 01 = 1，
0b00: 00 - 00 = 00 = 0。
分析下jdk的源码

1. i - ((i >>> 1) & 0x55555555);

首先i右移一位，左位变右位，然后&0x55555555丢弃左位，也就是保留原来i的左位。
最后用数字本身去减，得到结果，与(n & 0x55555555) + ((n >>> 1) & 0x55555555)相比，
节约了一次位运算。

1. i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

这一步没有进行额外的优化，计算每4个bit中的1个数，就是分组错位计算相加，
0x33333333：清除每4位中左边的2个0，
先清除左边的2个0，然后右移2位，左2位变右2位，清0，两者进行相加得到结果。

1. i = (i + (i >>> 4)) & 0x0f0f0f0f;

这一步是计算每8个bit中1的个数，最多8个1，最大值是二进制1000，所以用4个bit就可以表示。
上一步计算4个bit中1的个数每一组最多是4(100)，需要占用3位，会产生溢出现象，
所以需要分别& 0x33333333进行清0。
在这一步，4个bit已经足够表示结果，所以右移4个bit后不需要进行清0操作，然后直接进行相加，
左边的4位不影响运算结果，最后& 0x0f0f0f0f 清除左位的4个0。

1. i = i + (i >>> 8);

这一步计算每16位中的1的个数，最多10000，占5位，最后每一组左位的8个数他不进行清0了，留在最后统一清0。

1. i = i + (i >>> 16);

这一步计算32位中的1的个数，最多100000，占6位，同样不进行清0。

1. return i & 0x3f;

最后一步，清0
0x3f：00000000 00000000 00000011 1111
只保留低6位，低6位刚好能够表示32位二进制数中1的个数的最大值，前面全部舍弃。

总结

这个做法其实主要不是为了处理int，而是为了处理更大的位数，可以找到它的引用全在BigInteger中。
在长度只有 32 位的 int 的情况下，该做法不一定就比循环要快（该做法会产生多个的中间结果，导致赋值发生多次，而且由于指令之间存在对 n 数值依赖，可能不会被优化为并行指令）。