Fast Integer Log2 function in C/C++
Some times, it happens that you need to have a high performance function that you usually use in a not optimized way. And since you never needed to optimize it you hesitated before realising it can be severly improved. Probably, this is what you would think of the integer log2 function, in general this function is used on not critic code so it can be “slow” without creating any problem (often used to calculate the size of a power of 2 texture to hold an image)
The usual way of calculating this log2 function is testing until the base elevated to the log is bigger than the value. This is easy with the << operator.
This function returns the truncated to the integer unit log2 of value:
{
unsigned int l = 0;
while( (value >> l) > 1 ) ++l;
return l;
}
Easy, isn’t it? And it is quite fast! you will do 8 comparations to return the log2 of 256.
But what if we do a binary search instead of this linear search …
{
unsigned int f=0, s=32;
while(s) {
s>>=1;
if( value > 1<<(f+s) ) f+=s;
}
return f;
}
Even faster since we will be doing a fixed number of comparations.
And so, if they are fixed …
{
register unsigned int l=0;
if(x >= 1<<16) { x>>=16; l|=16; }
if(x >= 1<<8) { x>>=8; l|=8; }
if(x >= 1<<4) { x>>=4; l|=4; }
if(x >= 1<<2) { x>>=2; l|=2; }
if(x >= 1<<1) l|=1;
return l;
}
You can hardcode the answers and the bit settings, and this one compiles really well!
If you want to go further you can expand the ifs to 32 branches with 32 results, and so you will collapse the search time to the minimal (I cannot think on something better), but it is up to you if you want to go further. As well this function can be bounded with template arguments, but I don’t think this will ever pay off.
Probably you won’t find this function useful (except if you are here because you were looking for it), but in any case I liked this function so much and I wanted to share it because it shows us that even the most every day used things can be improved, refined, and can be prepared for different contexts. It isn’t all invented, you can keep discovering and creating 
- Juan Pablo
cristina Said,
April 2, 2009 @ 8:01 pm
it is not equal or bigger.
it is the last smaller or equal
Juan Pablo Said,
April 3, 2009 @ 3:21 am
You are right!
Corrected, thanks!
Eric Thiele Said,
January 15, 2010 @ 3:36 am
on x86 arch you can do it event faster…
bsr eax,eax
input and output are the eax register
bsr out,in (bit search reverse) searches the last enabeld bit in and writes position in out. (position last enabled bit ist the log2)
Juan Pablo Said,
January 15, 2010 @ 3:51 am
Yeah!
My head is programmed to write multiplatform code but I should have mentioned it anyway since it is way easier and probably the way to go on intel machines.
Thanks
Joonas Kekoni Said,
March 12, 2010 @ 6:18 am
Thanx. I was looking for this.
Marcos Said,
June 15, 2010 @ 9:59 am
Thanks!