개요
이번 글에서는 양수를 하나 입력받아 해당 숫자가 2의 거듭제곱인지 아닌지에 따라 불리언(Boolean) 값을 반환하는 함수 isPowerOfTwo()를 작성해 보겠습니다.
예를 들어 다음과 같은 결과가 나와야 합니다.
console.log(isPowerOfTwo(3)); // false
console.log(isPowerOfTwo(32)); // true
console.log(isPowerOfTwo(2048)); // true
console.log(isPowerOfTwo(256)); // true
console.log(isPowerOfTwo(22)); // false
재귀 함수를 활용한 구현
가장 직관적인 방법은 재귀 함수를 사용하는 것입니다. 로직은 매우 간단합니다.
- 숫자가 1이면 true를 반환합니다. (2⁰ = 1)
- 숫자가 2로 나누어 떨어지지 않으면 false를 반환합니다.
- 그렇지 않다면 숫자를 2로 나눈 값으로 자기 자신을 다시 호출합니다.
이 과정에서 숫자가 계속 2로 나누어 떨어져 최종적으로 1까지 도달하면 그 수는 2의 거듭제곱이고, 도중에 홀수가 되면 2의 거듭제곱이 아닙니다.
예제 코드
const isPowerOfTwo = num => {
if(num === 1){
return true;
}
if(num % 2 !== 0){
return false;
}
return isPowerOfTwo(num / 2);
}
console.log(isPowerOfTwo(3));
console.log(isPowerOfTwo(32));
console.log(isPowerOfTwo(2048));
console.log(isPowerOfTwo(256));
console.log(isPowerOfTwo(22));출력 결과
콘솔에는 다음과 같이 출력됩니다.
false
true
true
true
false
비트 연산을 활용한 더 효율적인 방법
재귀 대신 비트 연산을 사용하면 한 줄로 해결할 수 있습니다. 2의 거듭제곱을 이진수로 표현하면 항상 맨 앞 비트만 1이고 나머지는 모두 0입니다(예: 8 = 1000₂). 따라서 num & (num - 1)의 결과가 0이면 그 숫자는 2의 거듭제곱입니다.
const isPowerOfTwo = num => num > 0 && (num & (num - 1)) === 0;
console.log(isPowerOfTwo(3)); // false
console.log(isPowerOfTwo(32)); // true
console.log(isPowerOfTwo(2048)); // true
이 방법은 재귀 호출 없이 상수 시간(O(1))에 처리되므로 성능 면에서 더 유리합니다. 단, 입력값이 반드시 양수여야 하므로 num > 0 조건을 함께 검사해 주는 것이 안전합니다.