未分類

Hamming Distance

BitManipulation, Go, 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 and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

For Example:

1
2
3
4
5
6
7
8
9
10
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.
提示 解題應用
BitManipulation XOR,AND

Default:

1
2
3
func hammingDistance(x int, y int) int {
}

解答思路:

如果要找出兩數在二進制中相異的部分有多少個，其實就只要直接將兩數做XOR就會是相差的部分了，剩下的只要算出做完XOR後共有多少個1在裡頭就大功告成了，而如果要計算二進制有多少個1出現，有一個小技巧是不斷的將”該數”與”該數-1”做AND直到0為止共做了多少次就會是有多少個1了，所以最後結合上述兩個流程就會是兩數在二進制中相異1的數量。

程式碼解說:

一開始將兩數XOR，這邊我們將x與y做XOR後再放回x中，接著就要計算剛才做完計算得到差異的部分共有多少個1，利用一迴圈不斷的將x與(x-1)做AND，直到x歸0為止，期間所做的次數就是最後1的數量，也就是兩數在二進制中相異部分的數量

1
2
3
4
5
6
7
var count int
x ^= y
for x != 0 {
	x = x & (x - 1)
	count++
}
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
func hammingDistance(x int, y int) int {
	var count int
	x ^= y
	for x != 0 {
		x = x & (x - 1)
		count++
	}
	return count
}

總結:

要找出兩數在二進制中相異的部分有多少個，先直接將兩數做XOR就會是相差的部分，再來計算得到的差異部分在二進制中有多少個1，就是不斷的將”該數”與”該數-1”做AND直到0為止共做了多少次就會是兩數在二進制中相異1的數量。

分享到