闭门造车姚师傅

Hamming Weight, 一个串中非零元素的个数

字数统计: 1k阅读时长: 4 min
2017/03/04 Share

汉明重量是一串符号中非零符号的个数,在最为常见的数据位符号串中,它是1的个数。

操作简单,贴近底层,在包括信息论、编码理论、密码学等多个领域都有应用。

Java中有Integer.bitCount()的实现。

发现这个问题源于LeetCode上的一个问题,bitCount。要求给定一个上界,输出从0到该上界的范围内所有数的二进制表示中1的个数,时间复杂度为O(n)。这就要求处理每个数的二进制表示的时间复杂度为O(1)。用循环显然是不可能了,循环相除的时间复杂度为O(logN)。所以,应该把思路放到位运算上。

bitCount实现

Java中bitCount的代码:

1
2
3
4
5
6
7
8
9
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;
}

简单示例

表格来自Wikipedia,汉明重量

符号 二进制 十进制 注释
A 0110110010111010 原始数据
B = A & 01 01 01 01 01 01 01 01 01 00 01 00 00 01 00 00 1,0,1,0,0,1,0,0 A隔一位检验
C = (A >> 1) & 01 01 01 01 01 01 01 01 00 01 01 00 01 01 01 01 0,1,1,0,1,1,1,1 A中剩余的数据位
D = B + C 01 01 10 00 01 10 01 01 1,1,2,0,1,2,1,1 A中每个双位段中1的个数列表
E = D & 0011 0011 0011 0011 0001 0000 0010 0001 1,0,2,1 D中数据隔一位检验
F = (D >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1,2,1,1 D中剩余数据的计算
G = E + F 0010 0010 0011 0010 2,2,3,2 A中4位数据段中1的个数列表
H = G & 00001111 00001111 00000010 00000010 2,2 G中隔一位检验
I = (G >> 4) & 00001111 00001111 00000010 00000011 2,3 G中剩余数据的计算
J = H + I 00000100 00000101 4,5 A中8位数据段中1的个数列表
K = J & 0000000011111111 0000000000000101 5 J中隔一位检验
L = (J >> 8) & 0000000011111111 0000000000000100 4 J中剩余数据的检验
M = K + L 0000000000001001 9 最终答案

原理解释

1.二进制编码

我们用的二进制编码是有权重的,也就是出现在不同位置的1对这个数大小的影响是不一样的。通常来说,从右向左(从0开始计数)的权重分别是
$$
2^n
$$
比如,对于一个4bit的二进制数1111,从右向左的四个1的权重分别为[1, 2, 4, 8]

2.把各位的权重统一至1

显然,如果一个二进制表示权重都是为1的话,一个数的表示就由sum:a[n]*2^n变为sum:a[n]*2^0sum:a[n]。这种表示,也正是我们数数的方式。

需要做的就是把各个独立的位组合起来。在接下来,我们用表格中新增加的符号来表示对应的步骤。

  • 步骤A

    初始状态,十进制就是完全拆开的二进制。显然,把16个十进制加起来就是最终的结果。

  • 步骤B、C

    对每两位进行“交运算”

    • 交01,得到偶数位的十进制表示,这里十进制的数目只有步骤A的一半了
    • 右移一位交01,(右移把一半的位降了一个权重),得到奇数位的十进制表示,是步骤A十进制表示的另一半

    经过步骤BC,成功将一组十进制进行了对分。

  • 步骤D

    BC步骤得到两组十进制对应元素的权重是一样的,加起来。

    现在,十进制的数目是八位,只有一开始的一半了。

    这里十进制中的每个元素代表,二进制表示中每两位中的1的个数。

经过几次这样的操作,最终十进制的数目只有一位,即二进制表示中所有1的个数。就这样,bingo!


Happy Coding

Ref:

维基百科:汉明重量

LeetCode:bitCount

CATALOG
  1. 1. bitCount实现
  2. 2. 简单示例
  3. 3. 原理解释
    1. 3.1. 1.二进制编码
    2. 3.2. 2.把各位的权重统一至1