汉明重量: 统计二进制数中1的个数与JDK中的设计实现

在Redis位图文章中,曾说过利用位图做登录统计,今天就来看下是如何实现统计功能的, JDK中又是如何设计实现的.

先说明下统计要求:

统计一个数字其二进制表达式中数字位数为1(或者说非0) 的个数.

这种统计也叫汉明重量(Hamming weight).

1. 利用位的与计算做统计

利用位的与操作, 判断某一位是否为1;

1 & 1 = 1
1 & 1 = 0

整个流程如下: 判断数字n右数第一位是否为1,并计数;

同时将数字n右移1位, 并重复上述过程,直到数字n为0.

缺陷: 这种只适合计算大于0的数字, 因为小于0的数字,高位为1, 在右移的过程中,使每一位都变成了1(0xFFFFFFFF), 无法正确计算.

代码如下:

public static int bitCount(int n) {
int count = 0;
while (n > 0) {
if ((n & 1) == 1) {
            count++;
        }
        n = n >> 1;
    }
return count;
}

2. 优化后的与运算

为了解决负数的问题,需要对上述方式做些调整.

待统计的数字n保持不变, 将与其进行位操作的flag进行左移操作, 再进行比较统计.

代码如下:

public static int countOfBit1(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) != 0) {
            count++;
        }
        flag = flag << 1;
    }
return count;
}

3. JDK实现的位统计

在JDK中的Integer类中也有位统计的具体实现.

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

这段代码看起来很复杂, 但原理是比较简单的,

先2个一组, 求二进制1的个数, 并且用两位二进制存储在原处, 然后4个一组, 求二进制位1的个数, 再把它存储以4位二进制到原处, 以此类推, 再8个一组, 16个一组统计个数.

下面在看下代码实现过程:

1. 两位一组,统计1的个数

先看下数据i与统计值c的关系

通过统计值c与原数据i的关系, 可以发现减数= i >>>1

所以统计值 c = i - ( i >>> 1)

值得注意的是, 右移之后高位一定是0

那多余2位时,右移会产生一个问题: 高位部分右移的数据会影响低位计算.

例如: 二进制数i = 0110

根据表格和统计值表达式,预期结果为: 0001

实际右移结果: 0011

可以发现左数第二位’1’是从高位右移下来的,影响了预期结果, 为消除影响需处理掉右移下来的高位

处理方式: 对高位进行与01操作

整体表达式为: 0110 >>> 1 & 0101 = 0001

每2位一组的统计结果为:

c = i -(i >>> 1 & 0101) 
= i -(i >>> 1 & 0x5) 
= 0110 - 0001 
= 0101

高两位统计结果为1,低两位统计结果也为1,结果正确

所以Integer的每2位一组的统计值为

i - ((i >>> 1) & 0x55555555);

2. 每4位一组统计1的个数

在上面第一步的前提下, 将统计好的2位一组的数量,合并相加.

同样以二进制数据i = 0110 为例,

经过两位一组的统计后为: c = 0101

四为一组相加的结果为: 01 + 01 = 10

过程如下:

高位右移2位: 0101 >> 2 = 0001

低位去掉高位统计干扰,只保留低位: 0101 & 0011 = 0001

统计结果:

高位个数+低位个数= (0101 >> 2 ) + (0101 & 0011) =(0101 >> 2 ) + (0101 & 0x3) = 0001 + 0001 = 0010

需注意的是, Integer是32位, 在高位右移之后同样也排除来自更高位的干扰

正确的处理过程为:

高位个数+低位个数
= (0101 >> 2 & 0011) + (0101 & 0011) 
= (0101 >> 2 & 0x3 ) + (0101 & 0x3) 
= 0001 + 0001 
= 0010

所以,每4位一组统计过程为

(i & 0x33333333) + ((i >>> 2) & 0x33333333);

3. 每8位一组,统计1的个数

操作过程与上述步骤类似,每2个相邻的4位一组数据相加,并排除高位干扰.

即: i = (i + (i >>> 4)) & 0x0f0f0f0f;例如,经上述步骤计算后

                       i = 0010 0010 0010 0010
                  i>>> 4 = 0000 0010 0010 0010
              i +(i>>>4) = 0010 0100 0100 0100
                  0x0f0f = 0000 1111 0000 1111
(i + (i >>> 4)) & 0x0f0f = 0000 0100 0000 0100

与预期相同

4. 每16位一组统计与32位一组统计

具体过程和上述一样不在赘述

代码为:

i = i + (i >>> 8);i = i + (i >>> 16);

5. 高位清理

因为Integer型32位,最多有32个1,所以最多需要6位存储就足够,其余高位清理掉.

代码如下:

i & 0x3f

这种1的统计方式还有很多种,大多也都是利用位操作处理实现的.