19년 9월 1주차 : 수의 비밀

1. 문제 - 난이도 ★

해당 수가 2^k인지 판별하는 것이다.

 

2. 입력

10^18 이하의 자연수가 주어진다.

 

3. 출력

2의 거듭제곱이면 Yes, 아니면 No를 출력한다.

 

4. 알고리즘

먼저 바로 떠오르는 생각은 2로 계속 나누다가 나머지가 0이면 2의 거듭제곱이고 1이면 2의 거듭제곱이 아닌 수이다. 그러나 입력값을 보면 

절대로 안된다는 것을 알 수 있다.

 

그렇다면 다른 방법으로 접근해야한다. 바로 비트연산이다. 

 

2의 거듭제곱은 딱 한 비트만 1인 수이다. 

위와 같이 2의 거듭제곱은 비트 하나만 1이다. 

 

해당 수를 n이라고 했을 때, n & -n은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다. 따라서 2개 이상이 켜져있다면 n과 n & -n은 절대로 같을 수 없다. 그러나 2의 거듭제곱과 같이 하나만 1이라면 n과 n & -n은 같아진다. 

 

추가로, &연산자보다 ==연산자가 우선순위가 높으므로 반드시 n & -n은 ()로 감싸줘야한다.

 

5. 소스코드

n = int(input())
if n & (n-1) == 0:
    print('Yes')
else:
    print('No')