汉明距离

求x,y这两个数二进制位不同的个数
异或，x ^ y就是二进制位不同的那个数
求出x ^ y的二进制位为1的个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
  let n = x ^ y;
  let result = 0;
  while (n !== 0) {
    // 去除右边第一个为1
    n &= n - 1;
    result++;
  }
  return result;
};

为什么n &= n-1可以去除右边的第一个1
n-1就是找到第一个为1的位，然后减去1

举例：13

1
2
3
4
n   1101 -> (1101) -> (1100) -> (1000) -> 0000
n-1          1100      1010      0100
n&n-1        1100      1000      0000
            count++   count++   count++    3

结果就是3

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 ao 使用 Stellar 1.29.1 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。