汉明距离的快速计算方法

首先,所谓汉明距离,是说两个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硬件实现快……

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注