목록2의 거듭제곱 (1)

Hoon222y

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

12345if(n == n&-n) { printf("2의 거듭제곱!");}else{ printf("2의 거듭제곱 아님!");}cs +설명) 2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.n & -n 은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다.그렇기 때문에 2개 이상이 켜져있다면 n & -n와는 절대 같아질 수 없는 것이다.그리고 n에 비트가 하나만 켜져있다면 n & -n 은 그 비트만 켜진 수가 되므로 같게되는것이다. 출처) http://sgc109.tistory.com/130잘보고 배웠당 ㅎㅎ
코딩/사소한 팁 2017. 5. 25. 14:35
Prev 1 Next