C++로 4의 거듭제곱 판별하기

정수가 하나 주어졌을 때, 그 수가 4의 거듭제곱인지 아닌지를 판별하는 것이 이번 문제의 목표입니다.

예를 들어 입력값이 16이라면, 16은 4²(=16)이므로 결과는 True가 됩니다.

해결 접근 방법

이 문제는 비트 연산(bit manipulation)을 활용하면 매우 효율적으로 해결할 수 있습니다. 알고리즘은 다음 단계를 따릅니다.

num이 0보다 작다면 → false를 반환합니다.
num & (num - 1)의 결과가 0이 아니라면 → false를 반환합니다.
(num & 01010101010101010101010101010101)의 결과가 0이라면 → false를 반환합니다.
위 조건을 모두 통과했다면 → true를 반환합니다.

동작 원리 자세히 살펴보기

첫 번째 검사: 4의 거듭제곱은 항상 양수이므로, 음수가 입력되면 즉시 false를 반환합니다.

두 번째 검사: 2의 거듭제곱은 이진 표현상 비트가 딱 하나만 1입니다. n & (n - 1) 연산은 가장 오른쪽에 있는 1비트를 제거하는 효과가 있어, 그 결과가 0이면 해당 수는 2의 거듭제곱임을 의미합니다. 4의 거듭제곱은 반드시 2의 거듭제곱이기도 하므로, 이 조건을 만족하지 않으면 false를 반환합니다.

세 번째 검사: 0x55555555(이진수로 0101...0101 패턴)는 짝수 번째 비트만 1인 마스크입니다. 4의 거듭제곱(1, 4, 16, 64, ...)은 항상 짝수 위치의 비트에 1을 가지므로, 이 마스크와 AND 연산을 했을 때 결과가 0이 나오면 해당 수는 4의 거듭제곱이 아닙니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isPowerOfFour(int num){
        if (num < 0)
            return false;
        if (num & (num - 1))
            return false;
        if (!(num & 0x55555555))
            return false;
        return true;
    }
};
main(){
    Solution ob;
    cout << (ob.isPowerOfFour(64));
}

입력

출력

입력값 64는 4³이므로 프로그램은 참(1)을 출력합니다.