历史及应用

汉明重量是以理查德·卫斯里·汉明的名字命名的，它在包括信息论、编码理论、密码学等多个领域都有应用。

高效实现

在密码学以及其它应用中经常需要计算数据位中1的个数，针对如何高效地实现人们已经广泛地进行了研究。一些处理器使用单个的命令进行计算，另外一些根据数据位向量使用并行运算进行处理。对于没有这些特性的处理器来说，已知的最好解决办法是按照树状进行相加。例如，要计算二进制数A=0110110010111010中1的个数，这些运算可以表示为：

这里的运算是用C语言表示的，所以X >> Y表示X右移Y位，X & Y表示X与Y的位与，+表示普通的加法。基于上面所讨论的思想的这个问题的最好算法列在这里：

//types and constants used in the functions belowtypedefunsigned__int64uint64;//assume this gives 64-bitsconstuint64m1=0x5555555555555555;//binary: 0101...constuint64m2=0x3333333333333333;//binary: 00110011..constuint64m4=0x0f0f0f0f0f0f0f0f;//binary: 4 zeros, 4 ones ...constuint64m8=0x00ff00ff00ff00ff;//binary: 8 zeros, 8 ones ...constuint64m16=0x0000ffff0000ffff;//binary: 16 zeros, 16 ones ...constuint64m32=0x00000000ffffffff;//binary: 32 zeros, 32 ones ...constuint64hff=0xffffffffffffffff;//binary: all onesconstuint64h01=0x0101010101010101;//the sum of 256 to the power of 0,1,2,3...//This is a naive implementation, shown for comparison,//and to help in understanding the better functions.//It uses 24 arithmetic operations (shift, add, and).intpopcount_1(uint64x){x=(x&m1)+((x>>1)&m1);//put count of each 2 bits into those 2 bits x=(x&m2)+((x>>2)&m2);//put count of each 4 bits into those 4 bits x=(x&m4)+((x>>4)&m4);//put count of each 8 bits into those 8 bits x=(x&m8)+((x>>8)&m8);//put count of each 16 bits into those 16 bits x=(x&m16)+((x>>16)&m16);//put count of each 32 bits into those 32 bits x=(x&m32)+((x>>32)&m32);//put count of each 64 bits into those 64 bits returnx;}//This uses fewer arithmetic operations than any other known //implementation on machines with slow multiplication.//It uses 17 arithmetic operations.intpopcount_2(uint64x){x-=(x>>1)&m1;//put count of each 2 bits into those 2 bitsx=(x&m2)+((x>>2)&m2);//put count of each 4 bits into those 4 bits x=(x+(x>>4))&m4;//put count of each 8 bits into those 8 bits x+=x>>8;//put count of each 16 bits into their lowest 8 bitsx+=x>>16;//put count of each 32 bits into their lowest 8 bitsx+=x>>32;//put count of each 64 bits into their lowest 8 bitsreturnx&0xff;}//This uses fewer arithmetic operations than any other known //implementation on machines with fast multiplication.//It uses 12 arithmetic operations, one of which is a multiply.intpopcount_3(uint64x){x-=(x>>1)&m1;//put count of each 2 bits into those 2 bitsx=(x&m2)+((x>>2)&m2);//put count of each 4 bits into those 4 bits x=(x+(x>>4))&m4;//put count of each 8 bits into those 8 bits return(x*h01)>>56;//returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... }

在最坏的情况下，上面的实现是所有已知算法中表现最好的。但是，如果已知大多数数据位是0的话，那么还有更快的算法。这些更快的算法是基于这样一种事实即X与X-1相与得到的最低位永远是0。例如：

减1操作将最右边的符号从0变到1，从1变到0，与操作将会移除最右端的1。如果最初X有N个1，那么经过N次这样的迭代运算，X将减到0。下面的算法就是根据这个原理实现的。

//This is better when most bits in x are 0//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.intpopcount_4(uint64x){uint64count;for(count=0;x;count++)x&=x-1;returncount;}//This is better if most bits in x are 0.//It uses 2 arithmetic operations and one comparison/branch per "1" bit in x.//It is the same as the previous function, but with the loop unrolled.#define f(y) if ((x &= x-1) == 0) return y;intpopcount_5(uint64x){if(x==0)return0;f(1)f(2)f(3)f(4)f(5)f(6)f(7)f(8)f(9)f(10)f(11)f(12)f(13)f(14)f(15)f(16)f(17)f(18)f(19)f(20)f(21)f(22)f(23)f(24)f(25)f(26)f(27)f(28)f(29)f(30)f(31)f(32)f(33)f(34)f(35)f(36)f(37)f(38)f(39)f(40)f(41)f(42)f(43)f(44)f(45)f(46)f(47)f(48)f(49)f(50)f(51)f(52)f(53)f(54)f(55)f(56)f(57)f(58)f(59)f(60)f(61)f(62)f(63)return64;}//Use this instead if most bits in x are 1 instead of 0#define f(y) if ((x |= x+1) == hff) return 64-y;

参见

汉明距离

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。