LeetCode – 461. Hamming Distance

題目來源:LeetCode – 461. 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.

 

粗略翻譯:

漢明距離是兩個bit對應位置的不同的個數,舉例來說:

1的bit為0 0 0 1

4的bit為0 1 0 0

其中不同的個數有兩個,因此漢明距離為2


解法:

我自己的做法是如下所示:

每次都將x以及y做&1並比較是否不相同,如果不相同則diffCount+1

結束後再將x以及y向右位移1的距離,並再一次的比較。

Leetcode顯示這方法勝過了89%的人,執行速度10ms

 

另外我在Leetcode上看到有人有用一行的方式解出來,如下所示:

我用Leetcode跑出來顯示這方法勝過27%的人,執行速度13ms

速度比較起來只差3ms,幾乎差異不大,如果哪天真的需要計算漢明距離,

我個人應該還是頃向使用第二個方法吧


網站:http://wp.mlab.tw/
GitHub:https://github.com/yoll522/LeetCode
程式碼:https://github.com/yoll522/LeetCode/tree/master/461.%20Hamming%20Distance

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *