源码
/**
* 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
详细解释
-
设
i的二进制拆分表示为b0*2^0 + b1*2^1 + ... + b31*2^31 -
将
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
- 先令
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
- 将
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
- 将
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
- 将
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
- 将
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; }
-