파이썬(Python)으로 숫자가 2의 거듭제곱인지 판별하는 프로그램

이 글에서는 아래 문제에 대한 해결 방법을 자세히 알아보겠습니다.

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

이 문제는 크게 두 가지 방법으로 해결할 수 있습니다. 각 방법의 원리와 코드를 차례대로 살펴보겠습니다.

방법 1: 2로 반복해서 나누어 확인하기

2의 거듭제곱 수(1, 2, 4, 8, 16…)를 2로 계속 나누면 나머지 없이 마침내 1에 도달합니다. 반대로 2의 거듭제곱이 아니라면 나누는 과정에서 반드시 홀수가 등장합니다. 이 성질을 이용하면 숫자를 쉽게 판별할 수 있으며, 이는 log₂n이 정수인지 확인하는 것과 본질적으로 같은 원리입니다.

예제

# 2의 거듭제곱 판별
def find(n):
    if (n == 0):
        return False
    while (n != 1):
        if (n % 2 != 0):   # 나머지가 발생하면 2의 거듭제곱이 아님
            return False
        n = n // 2
    return True

# 드라이버 코드
if(find(98)):
    print('Yes')
else:
    print('No')

출력

No

98을 2로 나누면 49가 되는데, 49는 홀수이므로 'No'가 출력됩니다.

방법 2: 비트 연산(&) 활용하기

2의 거듭제곱 수는 이진법으로 표현했을 때 1인 비트가 단 하나뿐입니다(예: 8은 1000). 따라서 x와 x−1을 비트 단위 AND 연산하면 결과가 항상 0이 됩니다. 예를 들어 8(1000)과 7(0111)을 AND 연산하면 0000이 됩니다. 이 성질을 활용하면 반복문 없이 한 번의 연산으로 판별할 수 있어 훨씬 효율적입니다.

예제

# 2의 거듭제곱 판별
def find(x):
    # x가 0인 경우도 함께 처리
    return (x and (not(x & (x - 1))))

# 드라이버 코드
if(find(98)):
    print('Yes')
else:
    print('No')

출력

No

마무리

이 글에서는 반복적인 나눗셈과 비트 연산이라는 두 가지 방법으로 주어진 숫자가 2의 거듭제곱인지 확인하는 방법을 알아보았습니다. 반복 나눗셈 방식은 O(log n)의 시간이 걸리지만, 비트 연산 방식은 O(1)로 실행되므로 실무에서는 두 번째 방법을 사용하는 것이 더 효율적입니다.