PS와 개발을 공부하자

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

Algorithm/Memo &Tips

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

sgc109 2017. 5. 9. 15:37
1
2
if(n == (n&-n)) printf("2의 거듭제곱!");
else printf("2의 거듭제곱 아님!");
cs


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

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

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

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


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

4 Comments
댓글쓰기 폼