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

이 글에서는 주어진 문제를 해결하기 위한 해결 방법과 접근 방식에 대해 알아보겠습니다.

문제 설명

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

접근 방법

• 입력받은 숫자를 반복적으로 2로 나눕니다(n = n / 2).

• 각 반복 단계에서 n % 2 값이 0이 아니면서 n이 아직 1이 아니라면, 해당 숫자는 2의 거듭제곱이 아닙니다.

• n이 최종적으로 1이 된다면 그 숫자는 2의 거듭제곱입니다.

아래 구현 예시를 살펴보겠습니다.

예시

def isPowerOfTwo(n):
    if (n == 0):
        return False
    while (n != 1):
        if (n % 2 != 0):
            return False
        n = n // 2
    return True

# 메인 부분
if(isPowerOfTwo(40)):
    print('Yes')
else:
    print('No')

출력 결과

No

위 예시에서는 40을 입력값으로 사용했습니다. 40을 2로 계속 나누다 보면 중간에 홀수인 5가 되기 때문에 2의 거듭제곱이 아니며, 따라서 'No'가 출력됩니다.

모든 변수와 함수는 아래와 같이 전역 범위(global scope)에 선언되어 있습니다.

심화: 비트 연산을 활용한 더 효율적인 방법

반복 나눗셈 대신 비트 연산을 사용하면 한 번의 연산으로 판별할 수 있습니다. 2의 거듭제곱은 이진법으로 표현할 때 단 하나의 비트만 1입니다. 따라서 n & (n - 1) 연산의 결과가 0이라면 n은 2의 거듭제곱이라고 할 수 있습니다.

def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

print(isPowerOfTwo(64))  # True
print(isPowerOfTwo(40))  # False

결론

이 글에서는 반복적인 나눗셈 방식과 비트 연산 방식, 두 가지 방법을 통해 주어진 숫자가 2의 거듭제곱인지 판별하는 방법을 배웠습니다. 특히 비트 연산 방식은 시간 복잡도 O(1)로 동작하기 때문에 성능 면에서 매우 효율적입니다.