C++로 주어진 숫자가 4의 거듭제곱인지 확인하는 방법

이 문제에서는 정수 N이 주어지며, 주어진 정수가 4의 거듭제곱인지 아닌지 판별하는 것이 우리의 과제입니다.

문제 이해를 위한 예시

입력 : N = 64
출력 : Yes

설명 −

43 = 64

즉, 64는 4의 세제곱이므로 4의 거듭제곱에 해당합니다.

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 숫자를 반복적으로 4로 나누면서, 나눈 결과가 계속 4로 나누어떨어지는지 확인하는 것입니다. 재귀적으로 나누기를 진행한 후 값이 최종적으로 1이 되면 true를 반환합니다.

만약 나누는 도중 4로 나누어떨어지지 않는 값이 나온다면, 그 숫자는 4의 거듭제곱이 아니므로 false를 반환하면 됩니다.

알고리즘 단계

1. 입력값 n이 0이면 false를 반환합니다.
2. n이 1이 될 때까지 반복합니다.
3. 각 단계에서 n을 4로 나눈 나머지가 0이 아니면 false를 반환합니다.
4. n을 4로 나눕니다.
5. 루프가 종료되면 true를 반환합니다.

구현 예제

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;
bool isPowerOf4(int n){
   if(n == 0)
      return 0;
   while(n != 1)
   {
      if(n % 4 != 0)
         return 0;
      n = n / 4;
   }
   return 1;
}
int main(){
   int n = 123454;
   if (isPowerOf4(n))
      cout<<"The number is a power of 4";
   else
      cout<<"The number is not a power of 4";
   return 0;
}

실행 결과

The number is not a power of 4

시간 복잡도 분석

이 알고리즘은 매 반복마다 n을 4로 나누기 때문에 시간 복잡도는 O(log₄N)입니다. 즉, 입력값이 커져도 나눗셈 횟수가 로그 스케일로 증가하므로 매우 효율적입니다.

추가 팁: 비트 연산 활용하기

좀 더 최적화된 방법으로 비트 연산을 활용할 수도 있습니다. 4의 거듭제곱은 이진수로 표현했을 때 항상 홀수 번째 비트(0번째, 2번째, 4번째...)에 1이 하나만 있는 특징이 있습니다.

예를 들어, 어떤 수 x가 2의 거듭제곱인지는 (x & (x-1)) == 0으로 확인할 수 있으며, 여기에 x & 0xAAAAAAAA가 0인지 추가로 검사하면 4의 거듭제곱 여부를 O(1) 시간에 판별할 수 있습니다.