log(N)

CS345 이번 과제는 여러가지 해시 알고리즘을 직접 구현하는것이었다.

In the program spec, Dr. Moon wrote that a family of hash functions would be created by h sub k(s) = MyUtil.ELFhash(s, 2^k) for k > 0. Since M = 2^k, in order to find the value of k (so we can pass it into the argument of ElfHash when creating the extended function), we need to find the log2(M), am I correct? If so, how do I find this in Java? I cannot find any fuctions in Java’s math utility that returns the log base 2 of a number.

메일링 리스트에 대략 이런 내용의 글을 올린 사람이 있어서 잠시 log(N) 의 값을 구하는 방법에 대해서 생각해보게 되었다. 사실 구할 필요도 없긴 하지만.

log(N)
	c = 0
	while(N > 1)
		N = N >> 1
		c = c + 1
	end
	return c
end

대략 의사 코드(pseudo code)로 작성해보았다. 길이가 짧기도 하고 복잡한 조건도 없어서 아주 예뻐보인다 :D

public int log(int n) {
	int c = 0;
	while(n > 1) {
		n = n >> 1;
		c++;
	}
	return c;
}

자바로는 이렇게 구현하면 될까나… 어떤 언어든지 1분 내로 구현할 수 있다고 본다. 어셈블리어는 제외.

이미 눈치 챈 사람도 있겠지만, N 의 값이 2의 k제곱이 아닐때에는 결과값이 floor of log(N) 이 된다. 아~ 이거 의외로 쓸만할지도 모르겠다.