Log base 2 of an N-bit integer

Another Groovy training post. This time, three different method to find log base 2 of an N-bit integer.

Note: All algorithms and code credits goes to Bit Twiddling Hacks.

	def log2First(v) {
	def r = 0
	while ((v >>= 1) != 0) r++
	return r
	}
	def log2Second(v) {
	def buffer = java.nio.ByteBuffer.allocate(8)
	double d = buffer.putInt(0x43300000).putInt(v).getDouble(0) - 4503599627370496.0
	return (buffer.putDouble(0, d).getInt(0) >> 20) - 0x3FF
	}
	def log2Third(v) {
	def multiplyDeBruijnBitPosition = [
	0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
	8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	]
	[1,2,4,8,16].each { v |= v >> it }
	return multiplyDeBruijnBitPosition[ (v * 0x07C4ACDD) >> 27 ]
	}
	(1..100).each {
	assert log2First(it) == log2Second(it)
	assert log2Second(it) == log2Third(it)
	}

view raw gistfile1.groovy hosted with ❤ by GitHub

Note: All algorithms and code credits goes to Bit Twiddling Hacks.