2의 거듭제곱인지 O(1)에 판별하는 방법

if(n == (n&-n)) printf("2의 거듭제곱!");
else printf("2의 거듭제곱 아님!");

이유를 설명하자면 2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.

n & -n 은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다.

그렇기 때문에 2개 이상이 켜져있다면 n & -n와는 절대 같아질 수 없는 것이다.

그리고 n에 비트가 하나만 켜져있다면 n & -n 은 그 비트만 켜진 수가 되므로 같게되는것이다.

+그리고 & 연산자보다 == 연산자가 더 우선순위가 높으므로 괄호를 감싸는것을 잊으면 큰일난다..