2의 거듭제곱 수 인지 쉽게 확인하는 방법

2의 거듭제곱 수는 2진수로 표현했을 때 1이 하나만 존재하는 수입니다. 이를 이용하여 2의 거듭제곱 수인지 쉽게 확인할 수 있습니다.

코드

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

설명

• n > 0: n이 0보다 큰지 확인합니다. (음수는 2의 거듭제곱 수가 될 수 없습니다.)
• n & (n - 1): n과 n - 1을 AND 연산한 결과가 0이면 2의 거듭제곱 수입니다.
• 이진수 n에서 1을 빼면 1인 비트가 0으로, 0인 비트가 1로 바뀌게 됩니다. 이때 AND 연산을 하면 0이 나오게 됩니다.

ex1) n = 8(1000), n - 1 = 7(0111), n & (n - 1) = 0
ex2) n = 7(0111), n - 1 = 6(0110), n & (n - 1) = 6(0110)