C 언어에서 2의 거듭제곱 판별하기

숫자 n이 주어졌을 때, 이 수가 2의 거듭제곱인지 판별하는 문제는 코딩 테스트와 알고리즘 학습에서 자주 만나게 되는 대표적인 유형입니다. 예를 들어 n = 16이라면 결과는 true이고, n = 12라면 false가 됩니다.

핵심 아이디어: 비트 연산 활용하기

이 문제는 비트 연산(bitwise operation)을 사용하면 반복문이나 나눗셈 없이 O(1) 시간 복잡도로 해결할 수 있습니다. 2의 거듭제곱인 수를 이진수로 표현하면 최상위 비트(MSB)만 1이고 나머지 비트는 모두 0이라는 뚜렷한 특징이 있습니다.

1 = 0001
2 = 0010
4 = 0100
8 = 1000
16 = 10000

여기서 착안할 수 있는 점은, 어떤 수에서 1을 빼면 해당 수의 가장 오른쪽에 있는 1 비트가 0으로 바뀌고 그보다 낮은 자리의 비트들은 모두 1로 바뀐다는 사실입니다. 따라서 n AND (n − 1) 연산의 결과가 0이면 n은 2의 거듭제곱입니다.

n = 16인 경우를 직접 확인해 보겠습니다.

n     = 10000  (16)
n - 1 = 01111  (15)
---------------
AND   = 00000  (0)

두 이진수 사이에 겹치는 1 비트가 하나도 없기 때문에 AND 연산 결과가 0이 되며, 이를 통해 16이 2의 거듭제곱임을 단 한 번의 연산으로 판별할 수 있습니다.

C 언어 구현 예제

다음 코드를 통해 실제 구현 방법을 살펴보겠습니다.

#include <stdio.h>
#include <stdbool.h>

bool isPowerOfTwo(int n) {
    return (n > 0 && !(n & (n - 1)));
}

int main() {
    printf("%s\n", isPowerOfTwo(16) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(12) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(1) ? "true" : "false");
    printf("%s\n", isPowerOfTwo(32) ? "true" : "false");
    return 0;
}

입력 값

실행 결과

true
false
true
true

코드 상세 설명

isPowerOfTwo 함수는 두 가지 조건을 논리 AND(&&)로 묶어 동시에 검사합니다.

n > 0 — 0과 음수는 2의 거듭제곱이 될 수 없으므로 먼저 제외합니다.
!(n & (n - 1)) — n과 n−1의 비트 AND 결과가 0인지 확인합니다. 결과가 0이면 NOT 연산(!)을 거쳐 true가 반환됩니다.

참고로 일부 예제에 포함된 <math.h>나 #define MAX 20은 이 풀이에 실제로 필요하지 않으며, C99 이후 bool 타입을 사용하려면 <stdbool.h> 헤더를 포함하는 것이 올바른 방식입니다.

이 기법은 시간 복잡도 O(1), 공간 복잡도 O(1)로 매우 효율적이며, 하드웨어 수준에서 단일 명령으로 처리되는 비트 연산의 장점을 그대로 살린 최적화된 풀이입니다.

C 언어에서 2의 거듭제곱 판별하기 — 비트 연산 트릭

핵심 아이디어: 비트 연산 활용하기

C 언어 구현 예제

입력 값

실행 결과

코드 상세 설명