2022/07/06

Leetcode Note: Go - Hamming Distance

Hamming Distance - LeetCode
https://leetcode.com/problems/hamming-distance/

  • Go 言語で取り組んだメモ

所感

  • int x, y を 2進数 として Hamming distance を計算して、それらの距離を int として return する
  • Hamming distance の計算方法
    • int x, y を 2進数 に変換
    • x, y を何文字変更したら同じ数値にできるか算出
    • 例: x = 1, y = 4
      • x = 1 = 0001, y = 4 = 0100 なので、同じ数値にするなら 2 bit の変更が必要
    • 例: x = 3, y = 1
      • x = 3 = 0011, y = 1 = 0001 なので、同じ数値にするなら 1 bit の変更が必要

Hamming distance - Wikipedia
https://en.wikipedia.org/wiki/Hamming_distance

ハミング距離 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2

回答

Go | 100 % Faster - LeetCode Discuss
https://leetcode.com/problems/hamming-distance/discuss/1819749/Go-or-100-Faster

func hammingDistance(x int, y int) int {
	// Bitwise-XOR will give the number which have all the set bits for different corresponding btis
	xor := x ^ y
	r := 0
	// Calculate the number of set bits
	for xor != 0 {
		xor -= xor & (-xor)
		r++
	}
	return r
}
  • xor := x ^ y で x と y の排他的論理和を取得
  • for loop で xor と -xor の論理積をカウントして return

x, y を 2進数 に変換してからどうのこうのではなくビット演算で実装できる

See Also