題目連結:
題目意譯:
兩個整數間的漢明距離(The Hamming Distance)定為兩者有多少對應位元不相同。
給定兩整數 x 、 y ,計算漢明距離。
注:
0 ≦ x 、 y < 2 ^ 31.
範例測資:
輸入: x = 1 、 y = 4
輸出: 2
解釋:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭頭指出兩者對應的位元不相同的地方。
解題思維:
位元運算有一種操作,稱作互斥或(XOR),其有以下特性:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
也就是當兩個位元其中一者且僅有一者是 1 時,輸出結果才會是 1 。因此,我們可以藉由此操作找到兩數哪些位元不一樣。
將兩個數字作互斥或的運算,得出一個新的數字 C。將 C 按照一般漢明重量(Hamming Weight) 的計算方式(如
此題)即可求出原本的兩數有多少不同的位元。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。