LeetCode 231.

Approach 1. Loop

제일 간편하고 명확한 방법이다. loop를 돌면서 숫자를 계속 2로 나누다가 숫자가 1이 되면 True를 리턴하고, 숫자를 2로 나누었을 때 나머지가 0이 아니고 1도 아닌 경우에는 False를 리턴하도록 한다.

여기서 놓치지 않아야할 부분은 n == 0인 경우에는 반드시 False라는 점이다.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        while n != 1:
            n = n / 2
            if n % 2 != 0 and n != 1:
                return False
        return True

Approach 2. Bit manipulation

저번주에 Bit manipulation을 공부해서 정리하여 포스트를 썼었다. 그때 올렸던 Bit operator가 정리되어 있는 테이블을 다시 가지고 와서 보겠다.

이것을 어떻게 활용해볼지 생각해보자.
n을 2^x로 나타낼 수 있다면 이를 이진수로 나타내면 어떻게 될까?

n = 2   : 10
n = 2^2 : 100
n = 2^3 : 1000
....

맨 앞자리 1 빼고는 모든 숫자가 0이된다.

n-1 = 2-1   : 1   = 01
n-1 = 2^2-1 : 11  = 011
n-1 = 2^3-1 : 111 = 0111
....

고로 n은 b'1000...000
n-1 은 b'0111...111의 형태를 띈다.

결론:
n을 2^x로 나타낼 수 있다면
n AND n-1은 000...000 즉 0이 된다.

class Solution:
    def isPowerOfTwo(self, x: int) -> bool:
        if x == 0:
            return False
        return (x & (x - 1)) == 0