引子
目标
今天的标题是 “解读Integer.bitCount的源码”，也就是下面这一坨。但是，直接阅读可能会劝退自己，所以，今天我带你从一道简单的leetcode 算法题开始看起，只要你明白位运算的基本定义，跟着下面的步骤进行下来，相信你最终也可以读懂下面这段代码。
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;
}
题目
首先，从剑指 Offer 15. 二进制中1的个数这道算法题谈起，题目大意是给我们一个无符号的32位整数，让我们返回其中二进制形式中1的个数。
下面让我们一起看看这道题目大家都会有哪些解法？
思路
当然，这个问题的解决办法很多，这里只介绍个人觉得有代表性的三种方法，方便引出 最终源码级别的操作。
时间复杂度，也是从O(n)到O(1)逐步优化
1、直接遍历O(n)
对于大部分算法老司机来说，明白这题的意思之后，相信他们可以马上写出如下代码
var hammingWeight = function (n) {
let res = 0
while (n) {
res += (n & 1)
n >>>= 1
}
return res
};
上述代码的含义不需要赘述，这里作者暂时偷个懒🤗，搬运最近很火的charGPT的回答以飨读者 🤣
由于这个方法需要遍历32个二进制位，所以时间复杂度位O(k) k=32
2、每次清除最低位1O(log n)
第二种方法相对于第一种方法会巧妙一些，它利用n&n-1每次将n二进制中的最后一个1改成0，修改的次数即n中1的个数。
例如 7
7 --> 111 7-1 --> 110 n&n-1 110=6 第一次将最后一位1置为0
6 --> 110 6-1 --> 101 n&n-1 100=4 第二次将第二位1置为0
4 --> 100 4-1 --> 011 n&n-1 000=0 第三次将第一位1置为0
最终结果为3
var hammingWeight = function (n) {
let res = 0
while (n) {
n &= n - 1
res++
}
return res
};
总的来说，这个方法巧妙之处在于运用到 n&n-1这个操作每次可以把n的最后一位1置为0，从而统计出1的个数
由于这个方法的遍历次数取决于 n中的1的个数，所以均摊复杂度位log n
2、分治 O(1)
最后，就是大名鼎鼎的bitCount方法的介绍了。
首先，我们知道32位无符号整数占4个字节 一个字节有8个二进制位,1最多的数是0xffffffff，其中的一个f代表一段4个为1的二进制位 写成二进制的话也就是 11111111 11111111 11111111 11111111。
然后，对于一个二进制数，我们如果想每两位的遍历，可以如何做呢？当然，这里的遍历是指我们想将二进制位两两看成一组，然后取出其中的高位和低位。这话是什么意思呢？
例如
3的二进制是 11 我们想要做的就是将11看成一组，取出左边的1(高位) 和 右边的1(低位)，也就是 1 1
7的二进制是 111 我们想要做的就是将11看成一组，这里可能你要问，现在只有3个1，我们要怎么分组呢？
不明白的小伙伴可以看下面的解释，清楚的大佬可以直接跳过。
/*
当我们在写出一个数字的二进制形式时，其实是省略了他前面的0的，因为这样使得书写比较简便。
比如对于一个32位整数，它们的二进制形式是有32位的，我们之所以只写了后面的部分，是因为前面都是0
比如
7 -- 111 其实完整的二进制是 00000000 00000000 00000000 00000111
10 -- 1010 完整的二进制是 00000000 00000000 00000000 00001010
看吧，是不是写完整了之后，看起来也是很不方便，所以大家普遍都是只看后面有1的部分。
这样一来，也就不影响分组了。
*/
开始分组
书接上文，对于7=111 取出左边的1(高位) 和 右边的1(低位)，因为有两组 01、11，取出的高位和低位分别是0 1、1 1
知道了上面的之后，对于有效二进制位短的数，我们可以一眼看出来，
但是对于比较长的二进制串，我们是不方便直接获取的，也就是我们需要用一种方法可以一个数二进制中两两一组的 高位和低位。
两个二进制位为一组进行计数
对于2位的二进制串。比如 11，
我们可以将 11 & 10 就获取到了高位1，
用11 & 01 就获取到了低位的1。
为了让他们 & 相同的数字，我们可以将获取高位的方法改位 “先将11右移一位变成01，这样处在高位的1就到了低位。
然后就可以 & 01获取到此时低位的1”。
所以，获取高位的方法也可以使用 11 >>> 1 & 01。
这样一来，我们就将二位的二进制串中高位1的个数 算出来*重新*放到这两个二进制位上，
将低位1的个数也算出来并放到这两个二进制位上了。
又因为2个二进制可以存的最大数位11=3，这个数是大于 二个二进制位中1的个数的。这句话什么意思呢？
也就是说，刚刚我们使用11 >> 1&01 得到01=1，表示11这个二进制位中高位的1的个数是1个；
使用11 & 01得到01=1，表示11其中低位1的个数，那么，他们相加就得到了，这个2位的二进制串中1的个数。
又因为两个数字都是存放到2个二进制位上的，2个二进制位上的最大能表示3,而且3>2，
这样用能最大表示3的一个数字来表示2个二进制位中1的个数，就不会出现溢出的问题。
最后，我们就可以列出2位二进制串中1的个数的求解方法
(注意：js中使用0b作为前缀表示二进制数字)
let t = 0b01,num = 0b11
let cnt = (num >>> 1 & t) + (num & t)
第二步 可以简写成 let cnt = num - ((num >>> 1) & t)，少一次&运算，提升效率
表示 2个二进制位中1的个数 = 二进制表示的数字 - 高位的1的个数，例如：
11 = 3 - 1 = 2
10 = 2 - 1 = 1
01 = 1 - 0 = 1
也就是，两个二进制位上1的个数,可以通过这个二进制数减去高位1的个数得到
例如
11 - 1 = 2
01 - 0 = 1
四个二进制位为一组进行计数
当你明白上面2个二进制位中1的求解方法之后，同样的方法可以得到4个二进制位中1的个数，也就是
let t1 = 0b0101, t2 = 0b0011, num = 0b1101
num = num - (num >>> 1 & t)
let cnt = (num >>> 2 & t2) + (num & t2)
上面的操作含义是，对于数字1101，先将2个二进制看成一组，计算出每组中的1的个数，然后将它存储在当前的2个二进制位上。
即1001，10=2表示11这两个二进制位中1有2个，01=1表示01这两个二进制位中1有1个。
然后，在这个结果的基础上，将4个二进制位看成一组，计算每组中1的个数，然后将他们存储在当前的4个二进制位上
因为上面一步已经计算得到了每两位二进制中1的个数，所以此处将高两位1的个数 与 低两位1的个数相加，就可以得到结果。
即0011, 0011=3,表示1101这四个二进制位中1有3个。
八个二进制位为一组进行计数
和上面的思路一样，得到8个二进制位中1的个数，也就是
01010101 可以使用0x55555555代替
00110011 可以使用0x33333333代替
00001111 可以使用0x0f0f0f0f代替
num = 0b1011111111(十进制的767)
num = num - ((num >>> 1) & 0x55555555)
num = (num >>> 2 & 0x33333333) + (num & 0x33333333)
let cnt = (num >>> 4 & 0x0f0f0f0f) + (num & 0x0f0f0f0f)
其中最后一位 可以简写成 (num + (num >>> 4)) & 0x0f0f0f0f，少一次&运算，提升效率
为什么可以这样简写呢？
因为num >>> 4 表示num中高四位中1的个数，
而num可以看做是低四位中1的个数（因为后面 & 0x0f0f0f0f会将高四位都变为0）。
那么， num + (num >>> 4)就表示这8个二进制位中1的个数，
又因为4个二进制位能表示的最大数为0b1111=15 >8，所以用最大可以表示 15的数表示8个二进制位中1的个数不会有不够用的情况。
16个二进制位为一组进行计数
思路和8个二进制位完全一致，也就是
num = 0b1011111111(十进制的767)
num = num - ((num >>> 1) & 0x55555555)
num = (num >>> 2 & 0x33333333) + (num & 0x33333333)
num = (num + (num >>> 4) & 0x0f0f0f0f)
let cnt = num + (num >>> 8)
因为使用8个二进制位足以表示32位整数中1的个数，所以后面就可以不用切割，去掉前八位的值了
32个二进制位为一组进行计数
num = 0b1011111111(十进制的767)
num = num - ((num >>> 1) & 0x55555555)
num = (num >>> 2 & 0x33333333) + (num & 0x33333333)
num = (num + (num >>> 4) & 0x0f0f0f0f)
num = num + (num >>>> 8)
let cnt = num + (num >>> 16)
得到结果
num = 0b1011111111(十进制的767)
num = num - ((num >>> 1) & 0x55555555)
num = (num >>> 2 & 0x33333333) + (num & 0x33333333)
num = (num + (num >>> 4) & 0x0f0f0f0f)
num = num + (num >>> 8)
num = num + (num >>> 16)
let cnt = num & 0xff
由于使用0x3f也就是6个二进制位足以表示32位整数中1的个数，因为111111=63 > 32
所以，最后一行也可以写成 let cnt = num & 0x3f
思路成图
将整个过程按照分治思想，可以画出如下的图
体现的思想是：当我们直接计算32位二进制中1的个数很困难时，可以先计算每两个二进制位中1的个数，然后根据这个结果，再计算每四个二进制位中1的个数，进而得到8个二进制位中1的个数、16个二进制位中1的个数，最终得到整个二进制串中1的个数
767的二进制形式为00000000 00000000 00000010 11111111
二进制 十进制
1 0 1 1 1 1 1 1 1 1 10 11 11 11 11
01 10 10 10 10 1 2 2 2 2
\ / \ / / /
01 0100 0100 1 4 4
\ / \ /
01 1000 1 8
\ / \ /
1001 9
767的二进制中的1的位数计算过程
代码
方法1
var hammingWeight = function (n) {
let res = 0
while (n) {
res += (n & 1)
n >>>= 1
}
return res
};
方法2
var hammingWeight = function (n) {
let res = 0
while (n) {
n &= n - 1
res++
}
return res
};
方法3
var hammingWeight = function (i) {
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;
};