`__uint128_t_`

最近越来越多的协议会定义 16 字节长的整形，gcc 在 4.6 以上版本就可以使用 __int128_t & __uint128_t 了。

但需要注意的是，_uint128_t & __int128_t 仅对 64 位程序才有定义，因此如果编译选项中加入了 -m32，会出现找不到定义的编译错误。

另外 _uint128_t & __int128_t 并非 c/c++ 标准，所以 gcc 目前只支持基本运算符的操作，printf 这些都需要另外实现。

快速计算汉明距离

在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

汉明距离是以理查德・卫斯里・汉明的名字命名的。在通信传输过程中，累计定长二进制字中发生翻转的错误数据位，所以它也被称为信号距离。汉明距离在包括信息论、编码理论、密码学等领域都有应用。

对于两个字符串计算汉明距离，那肯定也就只能是逐位比较

//s1,s2为两个字符串，M为这两个字符串的长度
int hammingDistance(char s1[], char s2[], int M) {
    int dist = 0;
    int l1 = strlen(s1), l2 = strlen(s2);
    for (int i = 0; i < M && i < l1 && i < l2; ++i) {
        dist += s1[i] ^ s2[i];
    }
    return dist;
}

那么这样肯定是很慢的，如果可以转化两个整型的数，我们很容易想到利用到异或运算。

__uint128_t fingerprint = 0;
for(int l = 0; l < M; ++l){
    if(sumsignedweight > 0){
        fingerprint = (fingerprint << 1) | 1;
    }else{
        fingerprint = (fingerprint << 1) | 0;
    }
}

这样可以转换最高128位的两个01字符串。

那么就可以利用^运算来就算汉明距离了,由于异或运算的性质，得到的c的数位上为1说明ab的对应位不相同，反之则相同，那么我们就之需要计算c的二进制表示中数位为1的数目。这里可以按位采取&运算。

int hammingDistance(__uint128_t a,__uint128_t b){
    __uint128_t c = a ^ b;
    int dist = 0;
    while(c){
        if(c & 1){
            dist += 1;
        }
        c = c >> 1;
    }
    return dist;
}

布莱恩·克尼根算法

我们先观察如下一个现象：对于任意一个非零的二进制数 a（将其看作无符号数），考虑 a 和 a-1 的关系。由于 a 非零，那么 a 中总有一些位为 1。假设 a 中最低位的 1 处于从右向左数的第 N 位。那么，a 的第 N 位以及第 N 位以后的每一位的值和 a-1 的第 N 位及第 N 位以后的每一位的值均不同。

举个例子就很容易理解了。我们以 8 位数来描述。假设 a=10010000，根据上述描述，从右往左数的第一个 1 出现在第 5 位，那么有 N=5。同时可以计算出 a-1=10001111，可以看到，从第 N 位开始，a 的后缀是 10000，而 a-1 的后缀是 01111。满足上述描述的现象。

进一步地，我们可以发现，如果对 a 和 a-1 进行与操作，就会直接消去位于最后一位，也就是第 N 位的 1。还以上面的 a 为例，a & (a-1)=10000000。可以看到，我们不需要遍历，而是通过一次运算，就可以把 a 中的最后一个 1 消掉。如果我们一直重复这项操作，那么 a 里有多少个 1，我们就仅需要多少次 a & (a-1) 的操作，就能把 a 化为 0 了。而这个操作的次数正是我们所要求的。

那么计算汉明距离就可以改进为：

int hammingDistance(__uint128_t a,__uint128_t b){
    __uint128_t c = a ^ b;
    int dist = 0;
    while(c){
        dist += 1;
        c = c & (c - 1);
    }
    return dist;
}