題目

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

Hamming distance

Hamming distance 就如同題目所說的，是兩個字串對應位置的不同字符的個數，在兩個數字來說就是指對應的位元。
一開始是在錯誤校正碼(ECC)中所提出的定義，現在也用於許多不同的地方。

1. 比較圖片相似程度

在建立一個圖片哈希搜索引擎，每張圖片都會經過hash function得到一串64位元的數字，因為這hash function保留了與原圖的關聯性，所以當2張圖越相似，則hamming distance會越小。
有興趣能參考這個:
https://www.pyimagesearch.com/2019/08/26/building-an-image-hashing-search-engine-with-vp-trees-and-opencv/

2. Flip-N-write (FNW)

相變記憶體(phash change memory)是一種非易失性記憶體，每個bit有一定的寫入次數，表示你一直覆寫，那個bit就很會快壞掉，不能再使用。
能想到的就是逐位比較，當原本就是0，要寫的又是0，就不要寫這個bit了。但有可能會發生很多bit都是不同的，都要寫入!!
FNW algorithm的主要想法就是在寫入新資料時，先與舊資料逐位比對，當超過半數不一樣(即Hamming distance大於資料位元數的一半)，則會翻轉(flip)新資料，讓需要寫的bit變少(可控制在至少只要寫一半的bit)，且只要用1個bit去紀錄是否有翻轉這件事。

解法

1.使用XOR

根據XOR的規則，兩數字經過XOR後，是1的位元就是兩數字相應bit不同的位置，那我只要在計算有多少個1，就能得到結果啦。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorRes = x ^ y;
        int hd = 0;
        while(xorRes > 0){
            hd += xorRes % 2;
            xorRes >>= 1;
        }
        return hd;
    }
};

2.不使用XOR

不用XOR 就只是各別提取x,y的對應位元再比較

class Solution {
public:
    int hammingDistance(int x, int y) {
        int hd = 0;
        while(x > 0 || y > 0) {
            hd += (x % 2 != y % 2) ? 1 : 0;
            x >>= 1;
            y >>= 1;
        }
        return hd;
    }
};

3. 標準函式庫

c++中有一個class叫做 bitset，能將給進去的值(如下為x^y)，轉為給定位元數(如下為16)的2進制，並且有一個count功能，會回傳1的數量。

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> xorRes(x^y);
        return xorRes.count();
    }
};

那基本上3種方法的結果都差不多，如下: