[코딩 인터뷰 준비] 2의 제곱 찾기 알고리즘 - Power of Two

처음 이 문제를 받았을 때 저는 자신 있게 재귀 풀이를 짰습니다. 테스트 케이스 몇 개를 직접 돌려 보니 다 맞았고, 면접관도 고개를 끄덕였습니다. 그런데 “더 빠르게 할 수 있을까요?”라는 질문이 이어졌을 때, 저는 한참 침묵했습니다. O(log N)보다 빠른 방법이 있다는 것 자체를 그 순간엔 떠올리지 못했기 때문입니다. 그 면접에서 비트 연산 한 줄 풀이를 처음 접했고, 이후 LeetCode 토론에서 같은 실수를 반복하는 패턴을 여러 번 목격했습니다. 그 경험을 바탕으로 이 글을 정리합니다.

문제

주어진 정수가 2의 제곱인지 확인하는 메서드를 작성하십시오. (정수 범위는 Java의 Integer 범위와 동일합니다.)

예제 1:
Input: 1 / Output: true — 2^0 = 1

예제 2:
Input: 16 / Output: true — 2^4 = 16

예제 3:
Input: 218 / Output: false

면접 환경에서는 예제를 면접관이 알려주지 않는 경우가 많습니다. 먼저 예외 케이스부터 직접 떠올려야 합니다. 입력이 0일 때와 음수일 때는 항상 false입니다. 2의 거듭제곱은 절대로 0이나 음수가 될 수 없기 때문입니다.

재귀 풀이 — 제가 처음 시도한 방법

N이 2의 제곱이라면 2로 계속 나눌 때 홀수가 되기 전에 반드시 1에 도달한다는 성질을 이용합니다.

public boolean isPowerOfTwo(int n) {
    if (n == 1) return true;
    if (n <= 0 || n % 2 != 0) return false;
    return isPowerOfTwo(n / 2);
}

시간 복잡도 O(log N), 공간 복잡도 O(log N)(재귀 호출 스택)입니다. 면접관에게 “스택 프레임을 고려하지 않는다면 O(1)“이라고 주장할 수도 있지만, 엄밀히는 O(log N)으로 설명하는 것이 더 정확합니다.

반복문 풀이

같은 접근을 while 루프로 바꾸면 공간 복잡도가 O(1)로 줄어듭니다.

public boolean isPowerOfTwo(int n) {
    if (n < 1) return false;
    while (n % 2 == 0) n /= 2;
    return n == 1;
}

비트 연산 풀이 — O(1) 한 줄

면접에서 이 해법을 처음 봤을 때 저는 5분 가까이 들여다봐야 했습니다. 핵심 아이디어는 2의 거듭제곱은 이진수로 표현했을 때 1이 딱 하나만 있다는 성질입니다. n & (n - 1) 연산은 가장 낮은 비트 하나를 제거하므로, 2의 거듭제곱이라면 결과가 반드시 0이 됩니다.

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

직접 예시로 확인해 보겠습니다.

n = 8 → 이진수 1000, n - 1 = 7 → 0111. 8 & 7 = 0000. 결과: 0 (true)

n = 6 → 이진수 0110, n - 1 = 5 → 0101. 6 & 5 = 0100. 결과: 4 (false)

LeetCode 커뮤니티에서 자주 보이는 실수 두 가지

실수 1: n > 0 조건 생략. LeetCode 토론에서 가장 많이 나오는 Wrong Answer입니다. n = 0일 때 0 & (0 - 1) = 0 & -1 = 0이 되어 true로 잘못 판정됩니다. n > 0 조건이 반드시 필요합니다.

실수 2: n & (n + 1) 로 잘못 적기. n - 1이 아닌 n + 1로 쓰는 오타는 꽤 흔합니다. 두 연산은 완전히 다른 의미이므로 주의해야 합니다.

수학적 접근 — 2^30으로 나누기

Integer 최댓값이 2^31 - 1이므로, n의 최댓값은 2^30 = 1,073,741,824입니다. 2^k이면 2^30 % 2^k == 0이 성립한다는 성질을 이용합니다.

public boolean isPowerOfTwo(int n) {
    return n > 0 && (1073741824 % n == 0);
}

간결하지만 Java의 Integer 범위에 의존한다는 점을 면접관에게 반드시 언급해야 합니다. 다른 언어나 64비트 정수를 다루는 환경에서는 상수를 바꿔야 합니다.

해시 셋 접근

Integer 범위 안에 2의 거듭제곱은 딱 31개뿐입니다. 미리 셋에 넣어 두고 조회하는 방법도 가능합니다.

public boolean isPowerOfTwo(int n) {
    return new HashSet<>(Arrays.asList(1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
            1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
            524288, 1048576, 2097152, 4194304, 8388608, 16777216,
            33554432, 67108864, 134217728, 268435456, 536870912,
            1073741824)).contains(n);
}

시간·공간 복잡도 모두 O(1)이지만 하드코딩이라는 비판을 받을 수 있습니다. 면접에서 이 풀이를 내면 반응이 엇갈립니다. 실제로 저는 한 번 써봤는데, 면접관이 잠시 멈추더니 “창의적이네요”라고만 했습니다.

면접 팁

면접관이 “더 빠르게 할 수 있나요?”라고 물으면 비트 연산으로 바로 전환하십시오. 이때 n = 1, 4, 8을 직접 이진수로 그려 가며 설명하면 논리 전달이 훨씬 명확합니다. n > 0 조건이 필요한 이유를 스스로 먼저 언급하면 엣지 케이스를 챙기는 개발자라는 인상을 줄 수 있습니다.