526互联

Java的Integer.bitCount()源码分析

发布时间 2023-11-21 21:41:36作者: hlllz

本文部分参考：https://blog.csdn.net/weixin_42092787/article/details/106607426

常规解法

对于统计一个32位的二进制数值当中1的数量这个问题，常规解法如下：

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

jdk实现

上述方法通过移位运算判断每一位是否为1来统计数量。而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;
}

逐行解释：

i = i - ((i >>> 1) & 0x55555555);
目的：对于每2位，存储1的数量。
& 0x55555555的作用：保留奇数位，去除偶数位。
奇数位1的数量：i & 0x55555555
偶数位1的数量：(i >>> 1) & 0x55555555，偶数位右移到奇数位，原偶数位被按位与抹掉。
按理来说，此时i = i & 0x55555555 + (i >>> 1) & 0x55555555,我们猜测此时2种方式结果一样：
原来i：00 01 10 11
移i后：00 00 01 01
i减后：00 01 01 10
可以看到i减后的值巧妙地存储了原i 1的个数。
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
目的：对于每4位，存储1的数量。
做法：在1中每2位已经存储了1的数量。对于每4位，只需要将高2位+低2位即可实现。
这里就是基本做法无需解释。
i = (i + (i >>> 4)) & 0x0f0f0f0f;
目的：对于每8位，存储1的数量。
这里依旧没有选择常规做法，原理如下：
最大存储8个位刚好只需要1000一共4个位，所以无符号右移4位以后可以直接相加，并不会因为进位导致错误。
i = i + (i >>> 8);
目的：对于每16位，存储1的数量。
这里依旧没有选择常规做法，原理如下：
对于每8位而言在上一步中 & 0x0f0f0f0f;已经将高4位全部设置为0，而存储16位只需要5个位（10000），在此之前最多占用了4个位，就算不抹除高8位（& 0x00ff00ff）也不影响。
i = i + (i >>> 16);
目的：对于每32位，存储1的数量。
与上面类似，而存储32位只需要6个位（100000），距离上次清理来说，还有2个位可用（一个8个）。
return i & 0x3f;
最后&是保留最后2(11)+4(1111)=6个位的结果。事实上讨论到这里我们已经知道在6位只用到了100000。