[JS] Power of Two

🔒 문제 (LeetCode 231)

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Constraints:

• -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

 

🌊 입출력

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

 

---

 

🔑 해결

🌌 알고리즘 - 비트 조작

2^x 인 수 n을 이진수로 표현하면 가장 앞자리만 1이고 나머지는 0인 수가 된다. ex) 4 = 100(2), 16 = 10000(2)

이 때 n - 1 을 이진수로 나타내면 n보다 한자리 수 적고 모두 1로 구성된 수로 표현할 수 있다. ex) 3 = 11(2), 15 = 1111(2)

n이 2의 거듭제곱일 경우 n & (n - 1) 은 각 자리수가 다르기 때문에 0이 되야 한다. ex) 4 & 3 = 100 & 011 = 000

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {    
    // 비트 연산자
    return n > 0 && ((n & (n - 1)) === 0);
};