汉明重量是一串符号中非零符号的个数,在最为常见的数据位符号串中,它是1的个数。
操作简单,贴近底层,在包括信息论、编码理论、密码学等多个领域都有应用。
Java中有Integer.bitCount()的实现。
发现这个问题源于LeetCode上的一个问题,bitCount。要求给定一个上界,输出从0到该上界的范围内所有数的二进制表示中1的个数,时间复杂度为O(n)。这就要求处理每个数的二进制表示的时间复杂度为O(1)。用循环显然是不可能了,循环相除的时间复杂度为O(logN)。所以,应该把思路放到位运算上。
bitCount实现
Java中bitCount的代码:
1 | public static int bitCount(int i) { |
简单示例
表格来自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^0
即sum:a[n]
。这种表示,也正是我们数数的方式。
需要做的就是把各个独立的位组合起来。在接下来,我们用表格中新增加的符号来表示对应的步骤。
步骤A
初始状态,十进制就是完全拆开的二进制。显然,把16个十进制加起来就是最终的结果。
步骤B、C
对每两位进行“交运算”
- 交01,得到偶数位的十进制表示,这里十进制的数目只有步骤A的一半了
- 右移一位交01,(右移把一半的位降了一个权重),得到奇数位的十进制表示,是步骤A十进制表示的另一半
经过步骤BC,成功将一组十进制进行了对分。
步骤D
BC步骤得到两组十进制对应元素的权重是一样的,加起来。
现在,十进制的数目是八位,只有一开始的一半了。
这里十进制中的每个元素代表,二进制表示中每两位中的1的个数。
经过几次这样的操作,最终十进制的数目只有一位,即二进制表示中所有1的个数。就这样,bingo!
Happy Coding
Ref:
维基百科:汉明重量
LeetCode:bitCount