寻找最快的汉明距离C实现
我想找到两个等长的字符串有多少个不同的字符。 我发现xoring算法被认为是最快的，但它们返回以位表示的距离。 我希望结果以字符表示。 假设“pet”和“pit”的距离1以字符表示，但“e”和“i”可能有两个不同的位，因此xoring返回2。
我写的函数是：
// na = length of both strings unsigned int HammingDistance(const char* a, unsigned int na, const char* b) { unsigned int num_mismatches = 0; while (na) { if (*a != *b) ++num_mismatches; --na; ++a; ++b; } return num_mismatches; } 会变得更快吗？ 也许使用一些较低级别的命令或实现不同的算法？
系统：Intel Xeon X5650上的Gcc 4.7.2
谢谢
您可以通过对本机整数大小执行按位运算符，使您的比较一次比较更多字节。
在您的代码中，您一次比较一个字节的相等性，但您的CPU可以在一个周期中至少比较一个字，如果它是x86-64，则可以比较8个字节。 当然，确切的性能取决于CPU架构。
但是如果你通过大小为8的步幅推进两个指针，它在某些情况下肯定会更快。 当它必须从主存储器读取字符串时，内存加载时间实际上将主导性能。 但是如果字符串在CPU缓存中，您可能能够执行XOR，并通过测试64位值中位的更改来解释结果。
计算非0的桶可以使用SWAR算法的变体来完成，从0x33333333而不是0x55555555开始。
该算法将更难以使用，因为它将需要使用具有适当内存对齐的uint64_t指针。 你需要一个覆盖剩余字节的前导和后记。 也许你应该阅读编译器输出的程序集，看看在你尝试更复杂的代码之前它是不是做了更聪明的事情。
代替
if (*a != *b) ++num_mismatches;
在某些体系结构（8位字节）上这会更快，因为它避免了分支：
int bits = *a ^ *b; bits |= bits >> 4; bits |= bits >> 2; bits |= bits >> 1; num_mismatches += bits & 1;
循环展开怎么样：
while (na >= 8){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); num_mismatches += (a[4] != b[4]); num_mismatches += (a[5] != b[5]); num_mismatches += (a[6] != b[6]); num_mismatches += (a[7] != b[7]); a += 8; b += 8; na -= 8; } if (na >= 4){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); num_mismatches += (a[2] != b[2]); num_mismatches += (a[3] != b[3]); a += 4; b += 4; na -= 4; } if (na >= 2){ num_mismatches += (a[0] != b[0]); num_mismatches += (a[1] != b[1]); a += 2; b += 2; na -= 2; } if (na >= 1){ num_mismatches += (a[0] != b[0]); a += 1; b += 1; na -= 1; }
此外，如果您知道有很长的相等字符，您可以将指针强制转换为long*并一次比较4个，并且只有在不相等的情况下才能查看单个字符。 此代码基于memset和memcpy快速。 它将字符串复制到long数组中以1）消除对齐问题，以及2）用零填充字符串到整数个long s。 当它比较每对long s时，如果它们不相等，它会将指针转换为char*并计算不相等的字符。 主循环也可以展开，类似于上面的。
long la[BIG_ENOUGH]; long lb[BIG_ENOUGH]; memset(la, 0, sizeof(la)); memset(lb, 0, sizeof(lb)); memcpy(la, a, na); memcpy(lb, b, nb); int nla = (na + 3) & ~3; // assuming sizeof(long) = 4 long *pa = la, *pb = lb; while(nla >= 1){ if (pa[0] != pb[0]){ num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0]) + (((char*)pa[0])[1] != ((char*)pb[0])[1]) + (((char*)pa[0])[2] != ((char*)pb[0])[2]) + (((char*)pa[0])[3] != ((char*)pb[0])[3]) ; } pa += 1;pb += 1; nla -= 1; }
如果字符串用零填充，总是32字节，并且它们的地址是16对齐的，你可以这样做:(代码既不测试也不分析）
movdqa xmm0, [a] movdqa xmm1, [a + 16] pcmpeqb xmm0, [b] pcmpeqb xmm1, [b + 16] pxor xmm2, xmm2 psadbw xmm0, xmm2 psadbw xmm1, xmm2 pextrw ax, xmm0, 0 pextrw dx, xmm1, 0 add ax, dx movsx eax, ax neg eax
但如果字符串通常很小，它会做很多不必要的工作，而且可能不会更快。 如果字符串通常（接近）32字节，它应该更快。
编辑：我在看到你的更新评论之前写了这个答案 – 如果字符串通常很小，这可能不是很好。 一个16字节的版本可能（可能）是有用的（有条件地运行第二次迭代，应该很好地预测它的分支，因为它很少被采用）。 但是如此短的字符串，正常的代码很难被击败。
movdqa xmm0, [a] pxor xmm1, xmm1 pcmpeqb xmm0, [b] psadbw xmm0, xmm1 pextrw ax, xmm0, 0 movsx eax, ax neg eax