The method I use (for unsigned int) is branch based at the C code level but the compiler tends to use conditional moves for it on x86, here it is for reference:
#define log2i(n) ((((n) & 0xAAAAAAAA) != 0 ? 1 : 0) | (((n) & 0xCCCCCCCC) != 0 ? 2 : 0) | (((n) & 0xF0F0F0F0) != 0 ? 4 : 0) | (((n) & 0xFF00FF00) != 0 ? 8 : 0) | (((n) & 0xFFFF0000) != 0 ? 16 : 0))

I’d be curious to see a truly branchless version, although I think that one is fine if the compiler does a decent job :)

http://www.jjj.de/bitwizardry/bitwizardrypage.html

All those aside, I highly recommend Henry Warren Jr’s book Hacker’s Delight as the ultimate resource. It is well worth the ~$40 it costs.

Can anyone direct me to e-books, pdfs, articles, etc. on low level language tricks? Like, I read an article some while back about doing subtraction with clever addition and making use of the overflow. I lost the link to that article though..

I am interested in that kind of stuff. Mostly about tricks that are employed in writing code for embedded systems where every byte counts.

Thanks,
Norm

BitLog is the integer log2 of an integer value
Given an N-bit value, locate the leftmost nonzero bit.
b = the bitwise position of this bit, where 0 = LSB.
n = the NEXT three bits (ignoring the highest 1)

bitlog(x) = 8 x (b-1) + n

Bitlog is exactly 8 times larger than log2(x)-1