2의 거듭제곱 판별하기

 

 

2의 거듭제곱 판단하기

---

 

"어떤 자연수가 2의 거듭제곱임을 판별하라."

 

 

주어진 숫자가 $2^{63}$이하의 자연수라고 하면 당연히 2, 4, 8, 16, ... 순차적으로 확인해서 2의 거듭제곱인지 아닌지 판별하려고 할 것이다.

(물론 unsigned long long type으로 말이다.)

 

쿼리가 m개라면 $O(63m)$ 의 시간복잡도를 가질 것이다. 

물론 이것만으로도 충분히 빠른 판단이라 생각되지만 특별한 방법을 찾게 되어서 블로그에 남기기로 하였다.

 

결론부터 말하면

어떤 자연수 $n$에 대해

$$(n\mathrm{\&}(-n))==n$$

이면 그 수는 2의 거듭제곱이다.

 

결론을 알았으니 맞는지 잠시 생각해보자.

 

1) 우리가 찾고자 하는 2의 거듭제곱 수 $n$의 비트표현을 살펴보면 한 자리만 1이고 나머지는 모두 0인 수임을 알 수 있다.

예를 들어 $32$는 ${100000}_2$이고, $8$은 ${1000}_2$ 이다.

 

2) 주어진 수의 음수는 1의 보수를 취하고 1을 더하여 비트 표현을 구할 수 있는데, 2의 거듭제곱 수의 보수는 한 자리만 0이다.

이 수에 1을 더하게 되면 0이였던 자리를 포함하여 상위 비트는 모두 1이고 하위 비트는 0이 된다.

예를 들어 $32$는 1${00000}_2$인데, 보수를 취하면 $111...1$0${11111}_2$이고, 1을 더하게 되면 $111...1$1${00000}_2$가 된다.

 

3) 2의 거듭제곱 수가 아닌 경우에는 하위비트로 부터 상위비트로 읽어나갈 때 처음으로 나오는 1까지는 비트가 0이 되고, 처음 나오는 1은 1이며, 그 상위비트는 기존 비트의 반대가 된다.

예를 들어 $35$는 ${100011}_2$인데, $-35$는 $111..{.011101}_2$가 된다. 또 다른 예로는 $12$는 ${1100}_2$이고, $-12$는 $11..{.10100}_2$이다.

 

4) 따라서 2의 거듭제곱 수의 경우에는 $(n\mathrm{\&}(-n))==n$ 이 성립되고, 2의 거듭제곱 수가 아니라면 성립하지 않음을 알 수 있다.