欣迪

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

Given two integers x and y, return the Hamming distance between them.

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.

Example 2:

Input: x = 3, y = 1
Output: 1

Constraints:

  • 0 <= x, y <= 231 - 1

一開始蠻困惑,這個定義。還特別上維基百科查了一下。

資訊理論中,兩個等長字符串之間的漢明距離(英語:Hamming distance)是兩個字符串對應位置的不同字符的個數。換句話說,它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

漢明重量是字符串相對於同樣長度的零字符串的漢明距離,也就是說,它是字符串中非零的元素個數:對於二進位字符串來說,就是1的個數,所以11101的漢明重量是4。

例如:

  • 10111011001001之間的漢明距離是2。
  • 21438962233796之間的漢明距離是3。
  • toned“與”roses“之間的漢明距離是3。
var hammingDistance = function(x, y) {
    const sX = x.toString(2)
    const sY = y.toString(2)
    const range = Math.max(sX.length, sY.length)
    const stringX = sX.padStart(range, '0')
    const stringY = sY.padStart(range, '0')
    let distance = 0
    for(let i = 0; i < range; i++) {
        distance += stringX[i] !== stringY[i] ? 1 : 0  
    }
    return distance
};

我的做法是轉字串,不足補 0 ,再逐一比對文字。這是比較好懂的做法。

後來查了一下資料,有人提供了一行的解法,要使用 NOR ,蠻騷的做法,理解後再來發一篇吧。

var hammingDistance = function(x, y) {
    return (x ^ y).toString(2).replace(/0/g, '').length;
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。