[算法]汉明距离

Brian Kernighan 算法

两个整数之间的汉明距离是对应位置上数字不同的位数。

应用：广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。

优势： 避免逐一遍历

461. 汉明距离 （经典： 汉明距离）

方法： 按位异或

var hammingDistance = function(x, y) {
    let distance = x ^ y;
    let count = 0;
    while (distance != 0) {
        count++;
        distance &= (distance - 1);
    }
    return count;
};

按位异或

1 & 4  // 0
parseInt(1, 2) & parseInt(4, 2)  // 0
0001 & 0100  // 0
1 ^ 4 // 5

191. 位1的个数 （经典： 汉明重量）(剑指 Offer 15. 二进制中1的个数)

return~~ parseInt(n, ~~2);
方法： 掩码左移一位

var hammingWeight = function(n) {
    let count = 0;
    let mask = 1;
    for (let i=0; i < 32; i++) {
        if ((n & mask) != 0) {
            count++;
        }
        mask <<= 1;
    }
    return count;
};

移位运算

1 << 1  // 2
2 << 1  // 4

0b1 << 1  // 2
0b10 << 1  // 4

方法：Brian-kenigan算法（布赖恩-克尼根算法） n 按位与 n-1

var hammingWeight = function(n) {
    let count = 0;
    while (n != 0) {
        count++;
        n &= (n-1)
    }
    return count;
};

位运算
从低位的1进行统计， 相比仅遍历到count次， 效率更高

    0110
  & 0101
---------
        0100

方法：二进制

var hammingWeight = function(n) {
   let count = 0;
   while (n > 0) {
       if (n % 2 != 0) {
           count++;
       }
       n = Math.floor(n / 2)
   }
   return count;
};