題目描述

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



給定兩個整數,xy,回傳它們的漢明距離。

原題網址

輸入格式

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

輸出格式

輸出xy兩個整數的不同對應位元的數量。

範例輸入1

x = 1
y = 4

範例輸出1

2

額外解釋1

x = 1 = 00012
y = 4 = 01002

所以有2個位元不同。

範例輸入2

x = 3
y = 1

範例輸出2

1

題解

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

參考答案