本篇為LeetCode上演算法的簡單問題,Hamming Distance。
題目如下:
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers
x
andy
, 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.
兩個整數間的Hamming distance為其二進制的每個位元的差。請計算輸入參數兩整數x
與y
的Hamming distance
例如整數1的二進制為0 0 0 1
,而整數4的二進制為0 1 0 0
,則1與4的Hamming distance為2。
從題目的例子來看,馬上想到用位元運算子XOR
bitwise operator來計算兩整數二進位的位元差。但計算的結果為十進位,而Hamming distance是兩整數的每一位元有差異的個數,所以先轉成二進制,再來數1的部分有幾個。
public static int hammingDistance(int x, int y) {
int n = x ^ y;
int c = 0;
while (n > 0) {
c += n % 2;
n /= 2;
}
return c;
}
想了一下,改用位元移動運算子(bit shift operator)>>
來計算整數若為二進位時,有多少個1。
public static int hammingDistance(int x, int y) {
int n = x ^ y;
int c = 0;
while (n > 0) {
if ((n & 1) == 1) {
c++;
}
n >>= 1;
}
return c;
}
上面的if ((n & 1) == 1)
用來判斷整數是否為奇數(odd)。
調整一下。
public static int hammingDistance(int x, int y) {
int n = x ^ y;
int c = 0;
while (n > 0) {
c += n & 1;
n >>= 1;
}
return c;
}
更簡單的方法是用Integer.bitCount()
來取得整數在二進位有多少個1
public static int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
沒有留言:
張貼留言