bitCount源码解析

源码

/**
 * Returns the number of one-bits in the two‘s complement binary
 * representation of the specified {@code int} value.  This function is
 * sometimes referred to as the <i>population count</i>.
 *
 * @param i the value whose bits are to be counted
 * @return the number of one-bits in the two‘s complement binary
 *     representation of the specified {@code int} value.
 * @since 1.5
 */
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的数量的二进制
• 代码先一一分组计算二进制1的个数，再两两分组，再四四分组，以此类推直到算出整个32为int中的bitCount

参与运算的二进制含义

0x55555555 = 0101 0101 0101 0101 ...
0x33333333 = 0011 0011 0011 0011 ...
0x0f0f0f0f = 0000 1111 0000 1111 ...
0x3f = 0011 1111

代码流程

流程简介

• 行一将i两两分组，每组为这两位中二进制1的个数
• 按照原理，这行代码也可改写为(i & 0x55555555) + ((i >>> 1) & 0x55555555)
• 行二将i四四分组，每组为这四位中二进制1的个数
• 行三将i八八分组，每组为这八位中二进制1的个数
• 行四将i按十六位分组，每组为这十六位中二进制1的个数，这里也分为了4组，其中2组为垃圾数据
• 行四将i按三十二位分组，每组为这三十二位中二进制1的个数，这里也分为了4组，其中3组为垃圾数据
• 行五取出行四运算结果中的有效数据，6位二进制足够表示最大的32位int中的bitCount

详细解释

0. 设i的二进制拆分表示为b0*2^0 + b1*2^1 + ... + b31*2^31

1. 将i无符号右移一位，并与上0x55555555

- i >>> 1 后,
    i = b1*2^0 + b2*2^1 + ... + b31*2^30
        
- (i >>> 1) & 0x55555555 后,
	i = b1*2^0 + b2*2^1 + ... + b31*2^30
        - (b2*2^1 + b4*2^3 + ... + b30*2^29)
        
- i - ((i >>> 1) & 0x55555555) 后,
	i = b0*2^0 + b1*2^1 + ... + b31*2^31
        - (b1*2^0 + b2*2^1 + ... + b31*2^30
        - b2*2^1 + b4*2^3 + ... + b30*2^29)
      = b0*2^0 + b1*2^1 + ... + b31*2^31
        - (b1*2^0 + b3*2^2 + ... + b29*2^28 + b31*2^30)
      = b0*2^0 + b1*(2^1-2^0) + ... + b31*(2^31-2^30)
      = (b0+b1)*2^0 + (b2+b3)*2^2 + ... + (b30+b31)*2^30

2. 先令i与上0x33333333，再令i无符号右移两位后与上0x33333333，最后将这两部分相加

- 运算前, 原始的i已被两两位一组的分为16组, 每组表示这两位中二进制1的个数
	i = (b0+b1)*2^0 + (b2+b3)*2^2 + ... + (b30+b31)*2^30
- 运算后, 原始的i被四四位一组的分为8组，每组表示这四位中二进制1的个数
	i = (b0+b1+b2+b3)*2^0 + (b4+b5+b6+b7)*2^4 + ... +(b28+b29+b30+b31)*2^28

3. 将i无符号右移四位后加上i自己，并与上0x0f0f0f0f

- 运算后, i继续被八八位一组的分成4组, 每组表示这八位中二进制1的个数, 并且这八位中的前四位为0,, 因为4位二进制足够表示出每组中最大的数字8
	i = (b0+b1+b2+b3+b4+b5+b6+b7)*2^0
    	+ (b8+b9+b10+b11+b12+b13+b14+b15)*2^8
    	+ (b16+b17+b18+b19+b20+b21+b22+b23)*2^16
    	+ (b24+b25+b26+b27+b28+b29+b30+b31)*2^24

4. 将i无符号右移八位后加上i自己

- 运算后, i继续被分成4组, 但只有第一组和第三组是有效数据（每组表示这十六位中二进制1的个数）, 其他组为垃圾数据
	i = (b0+b1+b2+b3+b4+b5+b6+b7+b8+b9+b10+b11+b12+b13+b14+b15)*2^0
        + (b8+b9+b10+b11+b12+b13+b14+b15+b16+b17+b18+b19+b20+b21+b22+b23)*2^8
        + (b16+b17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27+b28+b29+b30+b31)*2^16
        + (b24+b25+b26+b27+b28+b29+b30+b31)*2^24

5. 将i无符号右移十六位后加上i自己

- 运算后, i继续被分成4组, 但只有第一组是有效数据（表示这32位中二进制1的个数）, 其他组为垃圾数据
	i = (b0+b1+...+b31)*2^0
        + (b8+b9+...+b30+b31)*2^8
        + (b16+b17+...+b30+b31)*2^16
        + (b24+b25+b26+b27+b28+b29+b30+b31)*2^24

6. 将i与上0x3f的值作为结果返回

- 运算后, 将上一步中第一组的有效数据提取了出来, 因为与上0x3f时大于2^5的数据都被置0, 而6位二进制足够表示32位int中的最大bitCount, 即32
	i = (b0+b1+...+b31)*2^0 & 0x00111111
      = (b0+b1+...+b31)*2^0
      = b0+b1+...+b31

例题

• 剑指Offer 15，题同LeetCode 191

  • 题目描述：请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2

    • 提示：
      a. 输入必须是长度为32的 二进制串
      b. you need to treat n as an unsigned value
      c. 位运算n & (n - 1)的作用是将n的二进制位中的最低位的1变成0
      d. 位运算n & -n的作用是得到n的二进制位中的最低位的1

  • 解1 - bitCount源码：

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

  • 解2 - 逐位判断：

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

  • 解3 - 位运算：

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

转自echofzoe‘s blog

bitCount源码解析

原文：https://www.cnblogs.com/okina-wa/p/14924236.html