C#에서 숫자가 2의 거듭제곱인지 판별하는 방법 총정리

2의 거듭제곱(Power of 2)이란 정수 n에 대해 2ⁿ 형태로 표현되는 수를 말합니다. 즉, 밑을 2로 하고 지수를 정수 n으로 하는 거듭제곱 연산의 결과값입니다.

대표적인 2의 거듭제곱 값은 아래 표와 같습니다.

방법 1: 비트 연산 활용 (가장 효율적)

2의 거듭제곱은 이진수로 표현했을 때 단 하나의 비트만 1이 된다는 특징이 있습니다. 예를 들어 8은 이진수로 1000이며, 여기서 1을 빼면 0111이 됩니다. 두 수를 비트 AND 연산하면 항상 0이 나옵니다.

따라서 (x & (x - 1)) == 0 조건에 0보다 큰지 여부까지 함께 검사하면, 반복문 없이 한 번의 연산으로 빠르게 판별할 수 있습니다.

class Program {
   static void Main() {
      Console.WriteLine(IsPowerOfTwo(9223372036854775809));
      Console.WriteLine(IsPowerOfTwo(4));
      Console.ReadLine();
   }
   static bool IsPowerOfTwo(ulong x) {
      return x > 0 && (x & (x - 1)) == 0;
   }
}

실행 결과

False
True

결과 해석: 9223372036854775809는 2의 거듭제곱이 아니므로 False, 4는 2²이므로 True가 출력됩니다.

방법 2: 반복문과 나눗셈 활용

비트 연산이 익숙하지 않다면, 수를 계속 2로 나누면서 나머지를 검사하는 직관적인 방식도 사용할 수 있습니다. 수가 홀수인데 아직 1이 아니라면 2의 거듭제곱이 아니며, 나눗셈을 반복해 최종적으로 1에 도달하면 2의 거듭제곱입니다.

class Program {
   static void Main() {
      Console.WriteLine(IsPowerOfTwo(9223372036854775809));
      Console.WriteLine(IsPowerOfTwo(4));
      Console.ReadLine();
   }
   static bool IsPowerOfTwo(ulong n) {
      if (n == 0)
         return false;
      while (n != 1) {
         if (n % 2 != 0)
            return false;
         n = n / 2;
      }
      return true;
   }
}

실행 결과

False
True

두 방법의 비교

두 코드 모두 동일한 결과를 출력하지만 성능에는 차이가 있습니다. 비트 연산 방식은 상수 시간(O(1))에 처리되므로 대용량 데이터나 성능이 중요한 환경에서 유리합니다. 반면 반복문 방식은 로그 시간(O(log n))이 걸리지만, 로직이 직관적이라 이해하기 쉽고 디버깅이 간편하다는 장점이 있습니다.