[Bit Manipulation] 231. Power of Two

https://leetcode.com/problems/power-of-two/ 

Power of Two - LeetCode

 

주어진 입력값이 2의 거듭제곱이면 true, 아니라면 false를 반환하는 문제

 

1) input : n = 1

output : true (2^0 = 1)

 

2) input : n = 16,

output : true  (2^4 = 16)

 

3) input : n = 3,

output : false (3은 2의 거듭제곱이 아님)

 

 

1. 반복문 (Iterative)

 - Time Complexcity :: O(logN)

 - Space Complexcity : (1) 

    class Solution {
    public:
        bool isPowerOfTwo(int n) {
            if(n == 0) return 0;
            while(n % 2 == 0) 
                n /= 2;
            return n == 1;
        }
    };

 

 

2. 재귀호출 (recursive)

 - Time Complexcity : O(logN)

 - Space Complexcity : O(logN) - 재귀호출 하는 만큼 스택에 쌓임

    class Solution {
    public:
        bool isPowerOfTwo(int n) {
            if(!n) return false;
            if(n == 1) return true;
            return n % 2 == 0 and isPowerOfTwo(n / 2);
        }
    };

 

 

3. Bit trick : n & (n - 1)) - Follow up: Could you solve it without loops/recursion?

 - Time Complexcity : O(1)

 - Space Complexcity : O(1) 

입력값 n을 2진수로 바꿔보면,

2의 거듭제곱 일 때는 1비트 + 거듭제곱의 수 만큼의 0비트 로 구성되어 있는 것을 알 수 있다.

n & (n - 1) 연산을 했을 때 결과가 0이라면 그것은 n이 2의 거듭제곱이라는 뜻이다.

 

    class Solution {
    public:
        bool isPowerOfTwo(int n) {
            return n > 0 && ((n & (n-1)) == 0);      
        }
    };