[Algorithm/Math] 비트 연산으로 log2 구하기

쉽게 구한다면 while(n>1) { n/=2; count++} 이런식으로 구할 수 있겠지만 곱하기(*) 나누기(/) 연산은 생각보다 엄청나게 느리다.

보통 더하기 연산의 수십배 이상 느린 곱하기, 나누기 연산이라고 했을 때.... 그래서 아래와 같이 바꿀 수 있는데

	public class LogUtil {
	static int log2 (int number) {
	int logCount = 0;
	if(65536 <= number) { logCount += 16; number >>= 16; }
	if(256 <= number) { logCount += 8; number >>= 8; }
	if(16 <= number) { logCount += 4; number >>= 4; }
	if(4 <= number) { logCount += 2; number >>= 2; }
	return logCount + (2 <= number ? 1 : 0);
	}
	}

view raw LogUtil.java hosted with ❤ by GitHub

뭔가 좀더 줄이고 싶다면 logBitCount 만에 구할 수 있다. 탐색문제나 log2로 무엇인가 구해야하는 문제가 나왔다면 곤란하기 짝이 없는데 아래와 같은 코드로 생각보다 쉽게 구할 수 있다(물론 정수 값만 가능하다.)