汉明距离的快速计算方法

首先，所谓汉明距离，是说两个01串之间不相同的0和1的个数。
比如： 1 1 0 1 1 和 1 0 1 0 1 的汉明距离就是3（中间三位不相同）
那么，怎么快速计算汉明距离呢？
这里给出三个方法，均以两个unsigned __int64的数a和b的汉明距离来做例子：

1）参考文章：http://crane.is-programmer.com/posts/17830.html

unsigned __int64 nHammingDist=a^b;

nHammingDist = (nHammingDist & 0x5555555555555555UI64) + ((nHammingDist>>1) & 0x5555555555555555UI64);
nHammingDist = (nHammingDist & 0x3333333333333333UI64) + ((nHammingDist>>2) & 0x3333333333333333UI64);
nHammingDist = (nHammingDist & 0x0f0f0f0f0f0f0f0fUI64) + ((nHammingDist>>4) & 0x0f0f0f0f0f0f0f0fUI64);
nHammingDist = (nHammingDist & 0x00ff00ff00ff00ffUI64) + ((nHammingDist>>8) & 0x00ff00ff00ff00ffUI64);
nHammingDist = (nHammingDist & 0x0000ffff0000ffffUI64) + ((nHammingDist>>16) & 0x0000ffff0000ffffUI64);
nHammingDist = (nHammingDist & 0x00000000ffffffffUI64) + ((nHammingDist>>32) & 0x00000000ffffffffUI64);


2）如果上述汉明距离需要频繁计算，那么，打表法不失为一种好方法。考虑到打表的大小要尽可能贴近L1缓存限制，所以考虑8bit计算一次：

static int Ham_count[256]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

unsigned __int64 temp=a^b;
uchar *uch=(uchar*)&temp;
int i,nHammingDist=0;
for(i=0;i<8;i++) { nHammingDist+=Ham_count[uch[i]]; }

3）如果CPU支持sse4.2指令集的话，可以用sse扩展指令快速计算（intel core 2以上CPU/amd 推土机以上CPU）

#include //需要这个头文件（VS2008及以上的VS。gcc之类的不清楚）
int nHammingDist=_mm_popcnt_u64(a^b);


那么，上述三种快速算法的时间代价分别是多少呢？
测试方法：1,000个256bit数，每个在100,0000个256bit数中间找最近的那个数。计算总计花费的时间。（单核2.8GHz intel core i5 460m）
下面是实验结果：
方法1: 56s
方法2: 53s
方法3: 34s

由此可见，打表法比折半计算稍快（实际如果多线程同时处理的话，方法2会比方法1快10%以上，因为方法1需要ALU计算，而方法2基本不需要ALU）
方法3的利用sse4.2指令的方法是最快的，但需要CPU支持（不过按照电脑每5年左右会淘汰一次的角度来看，过几年就都支持了）

总结：算法再快，不如CPU硬件实现快……