汉明距离 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 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
BYTE hmdistance1(BYTE a1, BYTE a2) { return hmd[a1][a2]; } BYTE hmdistance2(BYTE a1, BYTE a2) { BYTE val = a1 ^ a2; int num1 = 0; while (val) { ++num1; val &= val - 1; } return num1; } BYTE hmdistance3(BYTE a1, BYTE a2) { BYTE val = a1 ^ a2; int num1 = 0; while (val) { if (val & 0x01) ++num1; val >>= 1; } return num1; } BYTE hmdistance4(BYTE a1, BYTE a2) { BYTE val1 = a1; BYTE val2 = a2; int num1 = 0; for(int i=0; i<8; i++) { if ((val1 & 0x1) ^ (val2 & 0x1)) ++num1; val1 >>= 1; val2 >>= 1; } return num1; } |
第1种:最快,废空间
第2种:节省空间的情况下最快
第3种、第4种:差不多,3稍快