비트 연산을 이용해 2^n 이 맞는지 판별하기

문제를 풀다가 2^n이 맞는지 판별하기 위해서

 

while(){

 if(N==2)

 true

 

N % 2 ==1 

false;

 

N /=2;

 

}

 

로직을 구현한적이있다. 이러한 판별법은 2가 될때가지 구해서 판별한다. 하지만 비트연산자를 보면 

 

1 -> 1

2 -> 10

4 -> 100

8 -> 1000

 

보면 첫재 자리수 빼고는 전부 0인걸 알 수 있다.

 

결론부터 말하자면 밑에가 참이면 2의 제곱수이다.

if( N == (N&-N)) 

 

예를들어 8을 예시로 들겠다.

 

8을 비트로 만들면 1000 이된다.

 

-N = 2의보수 와같다.  과 같다. 따라서 1000 이된다. 앞전 부호비트 생략

 

1000

&

1000

은 1000 즉 N과 같게되서 위의 조건문을 만족한다.

 

만약 3일경우 11 은 01 이된다.

 

이처럼 N&-N 연산은 가장 오른쪽에 있는 1만 활성화시키는 비트연산이다. 

따라서 위의조건으로 1이 하나만 있는가?를 확인 할수가있다.

 

이처럼 쉽게 비트연산을 이용하여 2의제곲이 맞는지 검증할수가있다.