431. 漢明距離

思路

題目如標題所示。假設現在數字是 $\text{11111001}$，答案就是6。
方法跟190. 顛倒二進制位提到的差不多。

1. 取出數字 $n$ 奇數位與偶數位的數字1，
   奇數位 $\begin{array}{} n & \text{11111001} \\\text{mask} & \text{01010101} & \& \\\hline & \text{01010001} \end{array}$，偶數位$\begin{array}{} n\small{\gg}1 & \text{01111100} \\\text{mask} & \text{01010101} & \& \\\hline & \text{01010100} \end{array}$，
   再將兩個數字相加起來，代表讓「兩個位數」的資訊合併， $\begin{array}{} \text{01 01 00 01} \\ \text{01 01 01 00} & + \\\hline \text{10 10 01 01} \end{array}$。

此時每 4 位數字視為一個單位，代表這個單位當中有幾個1。
拿上面的例子來說，第一個單位 10 代表前兩位數一共有兩個 1 存在。

2. 接下來要讓四位數字視為一個單位，用類似的方法去做。
   前二位數字 $\begin{array}{} n & \text{10100101} \\\text{mask} & \text{00110011} & \& \\\hline & \text{00100001} \end{array}$，後二位數字$\begin{array}{} n\small{\gg}\blue{2} & \text{00101001} \\\text{mask} & \text{00110011} & \& \\\hline & \text{00100001} \end{array}$。
   將兩個數字相加， $\begin{array}{} \text{0010 0001} \\ \text{0010 0001} & + \\\hline \text{0100 0010} \end{array}$。 代表前面四位數有 4 個 1，後四位數有 2 個 1。

3. 最後讓八位數字視為一個單位。
   前四位數字 $\begin{array}{} n & \text{00100010} \\\text{mask} & \text{00001111} & \& \\\hline & \text{00000010} \end{array}$，後四位數字$\begin{array}{} n\small{\gg}\blue4 & \text{00000100} \\\text{mask} & \text{00001111} & \& \\\hline & \text{00000100} \end{array}$
   兩數相加， $\begin{array}{} \text{00000010} \\ \text{00000100} & + \\\hline \text{00000110} \end{array}$，代表八位數字中有 6 個數字1。

程式碼

位運算

class Solution {
public:
    int hammingDistance(int x, int y) {
        int n = x ^ y;
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555); // 一位, mask = 01...
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333); // 二位, mask = 0011...
        n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f); // 四位, mask = 00001111...
        n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff); // 八位, mask = 0x00ff...
        n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff); // 十六位, mask = 0x0000ffff
        return n;
    }
};

複雜度分析

• 時間複雜度：$O(1)$
• 空間複雜度：$O(1)$