Paul Kavanagh came up with an implementation of a log-base-2 function,
and just for fun I tried to beat him with something faster, written in
C. Here's my attempt. It breaks many of the rules we've talked about
in class (among other things, it is completely untested and I have not
measured its CPU time):
// log base 2 of the number of bits in an unsigned int.
enum { LG2_UINT_BITS = 5 };
// Verify that LG2_UINT_BITS is corrrect. This code is stolen from
// gnulib's verify module
// <http://www.gnu.org/software/gnulib/MODULES.html#module=verify>.
// Aren't C macros wonderful?
#define verify_true(R) (!!sizeof (struct { int dummy: (R) ? 2 : -2; }))
#define verify(R) extern int (* dummy (void)) [verify_true (R)]
verify ((unsigned int) -1 >> ((1 << LG2_UINT_BITS) - 1) == 1);
int floorLog2 (unsigned int n)
{
int r = 0;
for (int i = LG2_UINT_BITS - 1; 0 <= i; i--)
{
int shift = (1<<(1<<i) <= n) << i;
n >>= shift;
r += shift;
}
return r;
}
When compiled with gcc -std=gnu99 -O2 -S -funroll-loops
(GCC 4.2.2, x86) it generates the following assembly code. Look Ma, no conditional branches!
.file "t.c"
.text
.p2align 4,,15
.globl floorLog2
.type floorLog2, @function
floorLog2:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
movl 8(%ebp), %eax
movl %ebx, (%esp)
xorl %ebx, %ebx
movl %edi, 8(%esp)
movl %esi, 4(%esp)
cmpl $65535, %eax
seta %bl
xorl %edx, %edx
sall $4, %ebx
movl %ebx, %ecx
shrl %cl, %eax
cmpl $255, %eax
seta %dl
leal 0(,%edx,8), %edi
xorl %edx, %edx
movl %edi, %ecx
shrl %cl, %eax
cmpl $15, %eax
seta %dl
leal 0(,%edx,4), %esi
movl %esi, %ecx
shrl %cl, %eax
xorl %ecx, %ecx
cmpl $3, %eax
seta %cl
addl %ecx, %ecx
leal (%ebx,%edi), %edx
movl (%esp), %ebx
addl %esi, %edx
movl 8(%esp), %edi
shrl %cl, %eax
addl %ecx, %edx
movl 4(%esp), %esi
cmpl $1, %eax
seta %al
movl %ebp, %esp
popl %ebp
movzbl %al, %eax
addl %edx, %eax
ret
.size floorLog2, .-floorLog2
.ident "GCC: (GNU) 4.2.2"
.section .note.GNU-stack,"",@progbits