LeetCode Hamming Distance

本篇為LeetCode上演算法的簡單問題，Hamming Distance。

題目如下：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:

0 ≤ x, y < 231.

Example 1:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

兩個整數間的Hamming distance為其二進制的每個位元的差。請計算輸入參數兩整數x與y的Hamming distance

例如整數1的二進制為0 0 0 1，而整數4的二進制為0 1 0 0，則1與4的Hamming distance為2。

從題目的例子來看，馬上想到用位元運算子XOR bitwise operator來計算兩整數二進位的位元差。但計算的結果為十進位，而Hamming distance是兩整數的每一位元有差異的個數，所以先轉成二進制，再來數1的部分有幾個。

public static int hammingDistance(int x, int y) {
    int n = x ^ y;
    int c = 0;
    while (n > 0) {
        c += n % 2;
        n /= 2;
    }
    return c;
}

想了一下，改用位元移動運算子(bit shift operator)>>來計算整數若為二進位時，有多少個1。

public static int hammingDistance(int x, int y) {
    int n = x ^ y;
    int c = 0;
    while (n > 0) {
        if ((n & 1) == 1) {
            c++;
        }
        n >>= 1;
    }
    return c;
}

上面的if ((n & 1) == 1)用來判斷整數是否為奇數(odd)。

調整一下。

public static int hammingDistance(int x, int y) {
    int n = x ^ y;
    int c = 0;
    while (n > 0) {
        c += n & 1;
        n >>= 1;
    }
    return c;
}

更簡單的方法是用Integer.bitCount()來取得整數在二進位有多少個1

public static int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}