how to compute log2

[shareme]

I want to speed up fixed point math computations by using shifting..

so how do I compute Log2 of a number considering that I do not have access to Math.log?

[tom]

Here is a fixed point math library:
http://home.rochester.rr.com/ohommes/MathFP/

[davidaprice]

Log2(x) is just the opposite of 2^x.  So where 2^x is just "1 shifted left x times", log2(x) is just "the position of the left-most 1". E.g.:

log2(00000001b) = 0   ('b' suffix means binary here)
log2(00000100b) = 2
log2(10000000b) = 7

For numbers which aren't powers of 2, you must decide whether to round to the nearest integer or just round down. Rounding down is much easier . In which case:

log2(00000111b) = 2

Then your code will look something like this:

int log2 = 0;
while (x > 1) {
   log2++;
   x >>>= 1;
}

Note that I'm assuming x is positive! Negative numbers or zero would be invalid arguments for a log2 method.

If you're emulating fixed point (e.g. by storing all numbers << 8 ) then just subtract the number of fractional binary digits (e.g. 8 ) from the result of log2.

Games published by our own members! Check 'em out!

[shareme]

I foudn it in my knuth vollumes of books

let me explain why I want to sue it..

you can speed up fp math on non FPU cpus such as arm by shifting..ie


6*32=6<<log2 32=192

25/4 25>>log2 4=6

of course division is truncated and you have to allow for that

of course if I convert to binary before any computation than division is no longer truncated hey that works!

[shareme]

here is my solution and an example of where and how I am usng it:

http://www.jroller.com/page/shareme/20031213