Leetcode Note: Go - Number Complement

Number Complement - LeetCode
https://leetcode.com/problems/number-complement/

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

所感

• int num で渡される 10 進数の数値に対する complement (補数) を int で return する
• 例: num = 5 なら 2進数 にすると 101 なので補数は 010 になる 010 を 10進数 にすると 2 なので 2 を return する

回答

Golang solution faster than 100% bit manipulation - LeetCode Discuss
https://leetcode.com/problems/number-complement/discuss/1059500/Golang-solution-faster-than-100-bit-manipulation

func findComplement(num int) int {
	if num == 0 {
		return 1
	}
	res := 0
	g := 1
	for num > 0 {
		if num&1 == 0 {
			res += g
		}
		g <<= 1
		num >>= 1
	}
	return res
}

• num が 1 以上であればループ
  • ループ毎に g を 1bit ずつ左シフトで増やしていき、 num を 1bit ずつ右シフトで減らしていく
  • num&1 == 0 は num における一の位が 1 かどうかをチェックしている
    • num が偶数の場合は一の位は 0 となるので true になる
    • true なら res を増やして補数カウントを進める
    • ループ毎に num を右シフトしているので、いずれヒットする
      • num が 1 以上の数値であればいずれヒットするので、最初に num の 0 チェックを行っている