计算Hamming Distance汉明距离速度对比

汉明距离 Hamming Distance
两个二进制数不同的位,的数量
比如:
bin 001000
bin 000100
————–
第三位和第四位不同,所以它们的汉明距离为2
参考[ref]:
https://www.cnblogs.com/grandyang/p/6201215.html
https://blog.csdn.net/chouisbo/article/details/54906909

 

第1种:查二维表法,事先建一张256*256的表hmd
第2种:Wegner (1960) 提出了一种计算汉明权重(即计算给定整数的二进制表示中1的个数)的算法,通过反复查找并消除最低的非零bit位来实现
第3种:移位
第4种:异或最末位,再移位

 

 

 

第1种:最快,废空间
第2种:节省空间的情况下最快
第3种、第4种:差不多,3稍快

发表评论