2의 거듭제곱 판별하기

 

 

2의 거듭제곱 판단하기

---

 

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

 

 

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

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

 

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

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

 

결론부터 말하면

어떤 자연수 \(n\)에 대해

\[(n\ \&\ (-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\ \&\ (-n)) == n\) 이 성립되고, 2의 거듭제곱 수가 아니라면 성립하지 않음을 알 수 있다.