문제: 입력값이 2의 거듭제곱인지 확인하라.
2의 거듭제곱인 수는 1로 세팅된 비트가 하나뿐이다.
모든 비트를 검사하는 방법보다 빠른 방법이 존재할까?
XOR? AND? OR? 보수? 2의 보수?
4비트 입력을 가지고 여러 가지 시도를 해 본 결과, 2의 거듭제곱, 즉 1로 세팅된 비트가 하나 뿐인 이진수는 x = ~((x-1) OR ~x))를 만족하는 반면, 1이 두 개 이상 포함된 수는 저 식을 만족하지 않는다. 아래 표는 4비트 입력에 대한 모든 경우의 수를 확인해 본 결과이다.
| x | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 |
| x - 1 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | |
| ~x | 1110 | 1101 | 1100 | 1011 | 1010 | 1001 | 1000 | |
| (x-1) OR ~x | 1110 | 1101 | 1110 | 1011 | 1110 | 1101 | 1110 |
| x | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| x - 1 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 |
| ~x | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 | 0000 |
| (x-1) OR ~x | 0111 | 1110 | 1101 | 1110 | 1011 | 1110 | 1101 | 1110 |
이유를 생각해 보니, 1이 하나뿐인 이진수 x는 아래와 같은 성질을 가진다.
(1) x - 1을 계산하면 1이 세팅된 비트가 0이 되고, 오른쪽 비트들이 모두 1로 바뀐다. 즉, 1이 없어지거나 1의 위치가 바뀐다.
(2) x를 반전하면 1이 세팅된 비트가 0이 되고, 왼쪽/오른쪽 비트들이 모두 1로 바뀐다.
(3) 따라서 (1) OR (2)를 계산하면, 정확히 ~x가 된다.
반면, 1이 두 개 이상인 이진수는 다른 성질을 가진다.
(1) x - 1을 계산하면 가장 낮은 자리의 1이 0이 되고, 그 오른쪽 비트들이 1로 바뀐다. 높은 자리의 1은 원래 위치에 그대로 남는다.
(2) (1) OR ~x를 계산하면, (1)에서 높은 자리의 1이 원래 위치에 남아있기 때문에 절대 ~x가 될 수 없다.
이 방법을 이용하면 문제를 O(1)의 시간복잡도로 해결할 수 있다.
public static boolean isPowerOfTwo(long x) {
return ((x - 1) | ~x) == ~x;
}