본문 바로가기

알고리즘

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

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


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



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