문제 개요
두 개의 숫자 x와 n이 주어졌을 때, 산술 연산자를 사용하지 않고 x가 2^n으로 나누어 떨어지는지 확인하는 문제입니다.
예를 들어, 입력이 x = 32, n = 5라면 출력은 True가 됩니다. 왜냐하면 32 = 2^5이기 때문입니다.
해결 아이디어
이 문제는 비트 연산자를 활용하면 간단하게 해결할 수 있습니다. 핵심 원리는 다음과 같습니다.
- 2^n은 이진수로 표현하면 1 뒤에 n개의 0이 붙은 형태입니다. (예: 2^5 = 100000₂)
- (1 << n) - 1을 계산하면 하위 n비트가 모두 1인 마스크가 만들어집니다. (예: 011111₂)
- x와 이 마스크를 AND(&) 연산했을 때 결과가 0이라면, x의 하위 n비트가 모두 0이라는 뜻입니다. 즉, x는 2^n으로 정확히 나누어 떨어집니다.
알고리즘 단계
- x AND ((1 << n) - 1)의 결과가 0이면 True를 반환합니다.
- 그렇지 않으면 False를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(x, n):
if (x & ((1 << n) - 1)) == 0:
return True
return False
x = 32
n = 5
print(solve(x, n))입력
32, 5
출력
True
동작 원리 상세 설명
x = 32, n = 5인 경우 단계별로 살펴보겠습니다.
- (1 << 5) = 100000₂ → 십진수 32
- (1 << 5) - 1 = 011111₂ → 십진수 31
- 100000₂ & 011111₂ = 000000₂ → 결과가 0이므로 True 반환
이처럼 시프트 연산(<<)과 비트 AND 연산(&)만 사용하면 덧셈, 뺄셈, 나눗셈 같은 산술 연산자 없이도 2의 거듭제곱으로 나누어 떨어지는지 빠르게 판별할 수 있습니다. 이 방법은 시간 복잡도가 O(1)로 매우 효율적입니다.