力扣 汉明距离 解题

官方有三种方式，还是挺容易理解的。
1.内置位计数器功能

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

2.移位实现位计数

int hammingDistance(int x, int y) {
    int s = x ^ y, ret = 0;
    while (s) {
        ret += s & 1;
        s >>= 1;
    }
    return ret;
}

我们不断检查最低位，如果最低位为1，那么计时器加一，然后我们令s整体右移一位，这样子s的最低位最终将被舍弃，原本的次低位就变成了新的最低位。我们重复这个过程直到，s=0 为止。这样计数器中就累计了 s 的二进制表示中 1 的数量。
3.Brian Kernighan算法

   int hammingDistance(int x, int y) {
    int s = x ^ y, ret = 0;
    while (s) {
        s &= s - 1;
        ret++;
    }
    return ret;
}

当我们计算出 s =x⊕y，只需要不断让 s = f(s)s=f(s)，直到 s=0 即可。这样每循环一次，s 都会删去其二进制表示中最右侧的 1，最终循环的次数即为 s 的二进制表示中 1的数量。