JavaScript에서 숫자가 유효한 4의 거듭제곱인지 확인하는 방법

문제 설명

하나의 정수 num을 유일한 인수로 받아, 해당 숫자가 유효한 4의 거듭제곱인지 판별하는 JavaScript 함수를 작성해야 합니다. 숫자가 4의 거듭제곱이라면 true를, 그렇지 않다면 false를 반환하면 됩니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const num1 = 2356;
const num2 = 16;

그렇다면 기대되는 출력은 다음과 같습니다.

const output1 = false; // 2356은 4의 거듭제곱이 아님
const output2 = true;  // 16 = 4²

반복문을 이용한 풀이

가장 직관적인 방법은 4의 거듭제곱 값을 차례대로 계산하면서 입력값과 일치하는지 비교하는 것입니다. 32비트 정수 범위에서 4의 거듭제곱은 최대 4¹⁵까지 존재하므로, 지수를 0부터 15까지 반복하면 충분합니다.

const num1 = 2356;
const num2 = 16;

const isPowerOfFour = (num = 1) => {
   let bool = false;
   for(let i = 0; i < 16; i++){
      if(Math.pow(4, i) === num){
         bool = true;
         return bool;
      }
   }
   return bool;
};

console.log(isPowerOfFour(num1));
console.log(isPowerOfFour(num2));

실행 결과

콘솔에는 다음과 같이 출력됩니다.

false
true

비트 연산을 이용한 더 효율적인 방법

반복문 없이 O(1) 시간 복잡도로 문제를 해결할 수도 있습니다. 4의 거듭제곱은 항상 2의 거듭제곱이면서, 비트가 1개만 설정되어 있고 그 비트가 짝수 번째 위치(0, 2, 4...)에 있다는 성질을 활용합니다.

const isPowerOfFour = (num = 1) => {
   return num > 0 && (num & (num - 1)) === 0 && (num & 0x55555555) !== 0;
};

(num & (num - 1)) === 0 조건은 해당 숫자가 2의 거듭제곱인지 확인하고, num & 0x55555555는 짝수 번째 비트에 값이 설정되어 있는지 검사하여 4의 거듭제곱임을 보장합니다. 예를 들어 8(2³)은 2의 거듭제곱이지만 첫 번째 조건만 통과하고 마스크 검사에서 걸러지기 때문에 false가 반환됩니다.

마무리

작은 범위의 입력이라면 반복문 방식으로도 충분하지만, 성능이 중요한 상황에서는 비트 연산 기반의 O(1) 풀이가 훨씬 효율적입니다. 입력값의 크기와 요구 사항에 따라 적절한 방법을 선택하시기 바랍니다.