统计二进制中1个数 – bitCount优化详解

int类型由32位二进制数组成，Java中Integer.bitCount(int i)算法统计二进制数中1的个数，本文依次介绍和分析其线性实现、对数优化和运算优化，欢迎评论交流和指出错误，为支持作者高质量产出请尊重作者的著作权利，转载请注明出处😊

线性实现

各位上的1和0恰好表示1的出现次数，统计各位和即可，即依次无符号右移取最低位计和，时间 \small O(n)，空间 \small O(1)

public int bitCount(int i) {
    int cnt = 0;
    while(i != 0) {
        cnt += (i & 0x01);
        i >>>= 1;
    }
    return cnt;
}

对数优化

每轮两两合并高i位和低i位的统计次数到2i位中，时间 \small O(log_2n)，空间 \small O(1)

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

运算优化

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

1位组合并优化

两两合并相邻1位组，每个一位组范围为0(0)-1(1)，表示1位组中1出现个数，合并结果为 0(00)-2(10)，需要 两位二进制数储存累计结果。朴素的想法是取高1低+取1低位：取低1位的方法是 i & 0x55555555，取高1位对齐低1位的方法是(i >>> 1) & 0x55555555。取高1位后应清空原高1位，否则无效位参与运算，导致本2位组运算错误，甚至产生进位至左侧相邻2位组导致运算错误

[]：正确累计结果 ()：未清空的无效位 {}：合并后的2i位组
合并前1位组：[1] [1] [1] [1] [1] [1] [1] [1]
原低位1位组：(1) [1] (1) [1] (1) [1] (1) [1]
原高位1位组：[1] (1) [1] (1) [1] (1) [1] (1)
右移高1位组：(0) [1] (1) [1] (1) [1] (1) [1]
清高位1位组：(0) [1] (0) [1] (0) [1] (0) [1]
未清高位合并：[01] [11] [11] [10]
正确合并结果：[10] [10] [10] [10]

下面是所有双位情形与正确统计结果的对应关系，根据此对应关系很容易看出双位-取高位也能达到同样的效果，两种运算方式是等效的一对一映射

双位-取高位不产生借位和进位，是独立的两位数减法。如果实现为 n = (n – n >>> 1) & 0x33333333; 取高位后未清空原高位，导致原高位右移参与了本2位组的运算，影响了本组的运算正确性，甚至产生连续借位，影响左侧两位组的运算正确性

\scriptsize
\frac{\begin{matrix} \quad & \dot1 \dot1|01\\  -&01|10\end{matrix}}
{\begin{matrix} \quad & 01|11 \end{matrix}}

正确的2位数减法实现为 i = i – ((i >>> 1) & 0x55555555)；相比加法实现 i = i & 0x55555555 + ((i >>> 1) & 0x55555555); 减少了一次与运算

4位组合并优化

四位一组相互合并时，每个4位组的范围为0(000)-4(100)，表示4位组中累积出现1的次数；合并结果为0(0000)-8(1000)，需要 四位二进制数储存累积和

第一点优化：对齐的高低4位组无需清空高4位即可加和。因为 结果是4位，每个4位组都不会向相邻的4位组产生进位，意味着4位组无效位不包含在运算结果中，不会冲掉左侧高位组的正确累积结果

第二点正确性保障：之后 合并8位组时，产生5位结果，意味着未清空的4位组无效位产生了向高4位组的进位，无效进位上溢至储存正确累计结果的4位组导致运算错误，所以应当清空合并后的高4位组无效位

[]：正确累计结果 ()：未清空的无效位 {}：合并后的2i位组
合并前4位组：[0100] [0100] [0100] [0100] [0100] [0100] [0100] [0100]
原低位4位组：(0100) [0100] (0100) [0100] (0100) [0100] (0100) [0100]
原高位4位组：[0100] (0100) [0100] (0100) [0100] (0100) [0100] (0100)
右移高4位组：(0000) [0100] (0100) [0100] (0100) [0100] (0100) [0100]
合后未清高位：{(0100)[1000]} {(1000)[1000]} {(1000)[1000]} {(1000)[1000]}
未清合8位溢出：{(0100 1000 110)[1 0001]} {(0001 0001 000)[1 0000]}
合后清空高位：{(0000)[1000]} {(0000)[1000]} {(0000)[1000]} {(0000)[1000]}
清后合8位正确：{(0000 1000 000)[1 0000]} {(0001 0000 000)[1 0000]}

提前清空高位： i = i & 0x0f0f0f0f + (i >>> 4) & 0x0f0f0f0f);
和后清空高位： i = (i + (i >>> 4)) & 0x0f0f0f0f;
两种清空高位方案等效，但和后清空高位 减少一次与运算

8、16位合并优化

八位一组相互合并时，每个8位组的范围为0(0000)-8(1000)，表示8位组中累积出现1的次数；合并结果为0(00000)-16(10000)，需要 五位二进制数储存累积和

同4位组合并分析，对齐的高低8位组加和后，累积和结果最多占用低5位，每个8位组都不会产生影响左侧相邻8位组的进位，且下轮合并最多产生6位也不向高8位组溢出，不影响正确位置中的累积结果，因此无需清空高8位；此时8位组中的高3位是0，也无需考虑清零

提前清空高位： i = i & 0x00ff00ff + (i >>> 8) & 0x00ff00ff);
无需清空高位： i = i + (i >>> 8);
不清空高位 减少两次与运算

同理16位组加和后范围为0(000000)-32(100000)，最终累积结果存储在低6位，高位如何不影响最终结果

提前清空高位： i = i & 0x0000ffff + (i >>> 16) & 0x0000ffff);
无需清空高位： i = i + (i >>> 16);
不清空高位 减少两次与运算

16位组合并后，此时高位还存在未清空的无效位，通过过滤低六位 11 1111 (0x3f) 得出结果
return i & 0x3f;

参考文献

java源码Integer.bitCount算法解析，分析原理（统计二进制bit位）
Java.Integer.bitCount(int)源码解析