[LeetCode] 231. Power of Two

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Power of Two

문제 유형 : 비트마스킹, 재귀

문제 난이도 : Easy

 

문제

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.

 

정수 n이 주어집니다. 2의 배수이면 true를, 아니면 false를 반환하시오.

 

풀이

https://riveroverflow.tistory.com/entry/%EB%B9%84%ED%8A%B8-%EC%97%B0%EC%82%B0-%EA%B0%80%EC%9E%A5-%EC%98%A4%EB%A5%B8%EC%AA%BD-1%EC%9D%84-%EC%97%86%EC%95%A0%EA%B8%B0

비트 연산: 가장 오른쪽 1을 없애기

n & n-1연산을 하면, n의 가장 오른쪽 1이 0이 된다.

2의 배수의 특징은, 이진수로 표현했을 때 1이 한 개라는 것이다

2 = 0b10

4 = 0b100

8 = 0b1000

16 = 0b10000

32 = 0b100000

..

n&n-1연산을 하였을 때 0이 된다면, 2의 배수가 맞다.

 

단순히 반복문이나 재귀를 통해서도 풀 수 있을 것이다.

 

코드

C++

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

Go

func isPowerOfTwo(n int) bool {
    return n > 0 && (n&(n-1)) == 0
}