거듭제곱 알고리즘 [백준 1629번 ] about algorithm HOT 1 OPEN

2의 제곱수인지 확인 !

ex) 16 -> 2^4 ( true )
ex) 218 -> false

2의 제곱인 숫자를 비트연산자로 표현해 보면
1
10
100
1000 ...
으로 맨 좌측 숫자가 1이고 나머지는 0이다.

즉, 입력받은 숫자가 2의 제곱인지 확인하려면 위의 형태인지를 순차적으로 확인하는 방법이 있지만
int는 32bit만 표현이 가능하고 더 큰 경우는 시간 초과!

n & (n-1)

• 위의 식이 0인지를 확인하면 된다!
• n은 좌측이 1 나머지가 0이며, n-1은 좌측 0이며 나머지가 모두 1인 상태이다!!
• 두 수를 and 연산자로 0이되는 지를 확인한다.

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

from algorithm.