[Leetcode] 231. Power of Two 문제풀이

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

Power of Two - LeetCode

문제 내용

주어진 정수 n이 2의 제곱인지 확인하는 문제

Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1

 

문제 풀이

2의 제곱근을 생각하면 bit로 표현했을 때 1인 개수가 1개인 숫자이다.

처음에는 loop를 돌면서 bit개수를 세고 판단하려고 했으나

O(1)번만에도 가능했다.

 

bit의 1이 1개이기 때문에 이 1을 없애고 0인지 확인하면 된다.

그리고 예외처리 2가지가 있는데

1. n == 0 이면 false
2. integer overflow 때문에 long 타입을 사용

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