주어진 숫자가 2의 거듭제곱인지 확인하는 프로그래밍 문제는 코딩 테스트와 알고리즘 학습에서 자주 등장하는 기본 문제입니다. 이 글에서는 C++을 활용해 숫자가 2의 거듭제곱인지 판별하는 여러 가지 방법을 소개합니다.
2의 거듭제곱이란?
2의 거듭제곱은 2를 여러 번 곱한 수를 의미합니다. 대표적인 예는 다음과 같습니다.
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 ...
22 = 4
25 = 32
210 = 1024
판별 방법
숫자가 2의 거듭제곱인지 확인하는 대표적인 방법은 두 가지가 있습니다.
첫 번째 방법은 로그를 이용하는 것입니다. 밑이 2인 로그를 취했을 때 결과가 정수라면 해당 숫자는 2의 거듭제곱입니다.
두 번째 방법은 반복 나눗셈입니다. 숫자 N이 짝수인 동안 계속 2로 나누고, 최종적으로 1이 되면 N은 2의 거듭제곱입니다. 만약 나누는 도중 홀수가 되거나 0이 된다면 2의 거듭제곱이 아닙니다.
C++ 예제 코드
다음은 반복 나눗셈 방식을 구현한 C++ 코드입니다.
#include <iostream>
using namespace std;
int main() {
int n = 8;
if(n > 0) {
while(n % 2 == 0) {
n /= 2;
}
if(n == 1) {
cout << "Number is power of 2" << endl;
}
}
if(n == 0 || n != 1) {
cout << "Number is not power of 2" << endl;
}
return 0;
}
코드 동작 원리
위 코드는 다음 순서로 동작합니다.
- 입력값 n이 양수인지 먼저 검사합니다.
- n이 짝수인 동안(나머지가 0인 동안) 계속 2로 나눕니다.
- 나눗셈이 모두 끝난 후 n이 1이라면 처음 값은 2의 거듭제곱입니다.
- n이 0이거나 1이 아니라면 2의 거듭제곱이 아니므로 해당 메시지를 출력합니다.
실행 결과
Input: 8
Output: Number is power of 2
비트 연산을 활용한 더 효율적인 방법
비트 연산을 사용하면 시간 복잡도 O(1)로 더 빠르게 판별할 수 있습니다. 2의 거듭제곱은 이진수로 표현할 때 단 하나의 비트만 1입니다(예: 8 = 1000₂). 따라서 n & (n-1) 연산의 결과가 0이면 n은 2의 거듭제곱입니다.
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}예를 들어 8(1000₂)과 7(0111₂)을 AND 연산하면 0000₂가 되어 0이 반환되므로, 8은 2의 거듭제곱임을 즉시 알 수 있습니다. 실무에서는 이 비트 연산 방식이 가장 널리 사용됩니다.