[LeetCode]漢明距離(Hamming Distance)

題目描述

兩個整數的不同對應位元的數量，即為漢明距離。

給定兩個整數，x和y，回傳它們的漢明距離。

原題網址

https://leetcode.com/problems/hamming-distance/

輸入格式

0 <= x, y <= 2³¹ - 1

輸出格式

輸出x和y兩個整數的不同對應位元的數量。

範例輸入1

x = 1
y = 4

範例輸出1

額外解釋1

x = 1 = 0001₂
y = 4 = 0100₂

所以有2個位元不同。

範例輸入2

x = 3
y = 1

範例輸出2

題解

一開始先將兩個32位元的整數做XOR運算，即可求出所有位元的漢明距離，其同樣也是32位元的整數型別。接著為了要計算這32位元的整數中等於1的位元數量，正常情況下我們必須先將其轉成二進制來運算。然而這個做法會很慢，所以我們可以事先建立好所有8位元整數的位元為1的數量的表，接著將32位元的整數分四次，每次8位元來計算其等於1的位元數量，最後將這四次查詢出來的數量加總之後就是我們要的輸出結果了！

參考答案

static ONES_256: [u8; 256] = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
];

impl Solution {
    pub fn hamming_distance(x: i32, y: i32) -> i32 {
        let d = x ^ y;

        let b: [u8; 4] = d.to_ne_bytes();

        b.iter().map(|&e| ONES_256[e as usize]).sum::<u8>() as i32
    }
}

const ONES_256 = [
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
];

const hammingDistance = (x: number, y: number): number => {
    const d = x ^ y;

    const b1 = d >>> 24;
    const b2 = d << 8 >>> 24;
    const b3 = d << 16 >>> 24;
    const b4 = d & 0xFF;

    return ONES_256[b1] + ONES_256[b2] + ONES_256[b3] + ONES_256[b4];
};