파이썬으로 숫자가 2의 거듭제곱인지 확인하는 방법

문제 개요

하나의 숫자 n이 주어졌을 때, 이 숫자가 2의 거듭제곱인지 아닌지 판별해야 합니다.

예를 들어 입력값이 n = 2048이라면, 2048은 2^11에 해당하므로 출력 결과는 True가 됩니다.

해결 방법

이 문제는 비트 연산을 활용하면 매우 효율적으로 해결할 수 있습니다. 접근 방법은 다음과 같습니다.

n이 0과 같다면 False를 반환합니다.
(n AND (n - 1))의 결과가 0이면 True를, 그렇지 않으면 False를 반환합니다.

이 방법이 작동하는 원리는 간단합니다. 2의 거듭제곱 수는 이진수로 표현했을 때 단 하나의 비트만 1입니다. 예를 들어 8은 1000, 16은 10000처럼 표현됩니다. 여기서 1을 빼면 해당 비트는 0이 되고 그보다 낮은 자리의 비트는 모두 1로 바뀌므로, n과 (n-1)을 AND 연산하면 반드시 0이 됩니다. 반대로 2의 거듭제곱이 아니라면 두 값 사이에 공통으로 켜진 비트가 남아 결과가 0이 아니게 됩니다.

예제 코드

아래 파이썬 구현 예시를 통해 더 자세히 이해해 보겠습니다.

def solve(n):
   if n == 0:
      return False
   return (n & (n - 1)) == 0

n = 2048
print(solve(n))

입력

출력

True