C ] 시간복잡도가 O(1)인 2의 거듭제곱 판별

 

 

 

int isPowerOfTwo(int n) {
    return (n && ((n & (n - 1)) == 0));
}

 

2의 거듭제곱은 가장 왼쪽에 있는 1을 제외하고 뒷부분이 전부 0이라는 걸 고려할 때 위와 같은 코드로 판별할 수 있다.

 

 

 

 

 

 

 

 

 

그리고 어떤 정수를 2의 거듭제곱 수로 나눈 나머지 연산을 해야할 때 성능향상을 위한 최적화 기법으로 %연산이 아니라 &연산을 쓰기도 한다. 위와 같은 논리이다.

 

#define SOME_NUMBER_POWER_OF_TWO	8

int getRemainder(int n)
{
	return n & (SOME_NUMBER_POWER_OF_TWO - 1);
}