2022/05/27

Leetcode Note: Go - Power of Two

Power of Two - LeetCode
https://leetcode.com/problems/power-of-two/

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

所感

  • 2の累乗かを判定する
  • ちなみに 0 は ２の累乗 ではありません！

回答

100% Bit-wise one-line solution (without loops/recursion) - LeetCode Discuss https://leetcode.com/problems/power-of-two/discuss/1504350/ 100-Bit-wise-one-line-solution-(without-loopsrecursion)

func isPowerOfTwo(n int) bool {
    if n > 0 {
        return n & (n - 1) == 0
    }

    return false
}
  • n & (n - 1) == 0 が肝で、ビット演算子を使うことで累乗の判定を行っている
    • 2の累乗の場合、 n と n - 1 をビット演算すると 0 になるという特性がある
      • 4 なら
        • 100 (4) - 011 (3) = 000 (0)
      • 3 なら
        • 011 (3) - 010 (2) = 010 (2)
    • そのため n & (n - 1) == 0 が true であれば 2の累乗 と判断して良い
  • 急にアンパサンドが出てきてポインタかと思ったがビット演算子だった
    • ビット演算子というか 2進数 を使った判定ができるというのが目からウロコだった

See Also