2의 거듭제곱인지를 O(1)에 알 수 있는 방법

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

+설명) 

2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.

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

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

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

출처) http://sgc109.tistory.com/130

잘보고 배웠당 ㅎㅎ