[LCP]Base 2 logarithms

[Vincent Penquerc'h]

> What's the best way to calculate base 2 logarithms?  I know 
> that I could
> use log(x)/log(2) or log10(x)/log10(2), but I'm not sure 

Of an int ?
If not an int, then floor it, and get the int, then:

unsigned int log2(unsigned int n)
{
  int l=0;
  while (n) {
    n>>=1;
    ++l;
  }
  return n;
}

That's the general idea, I might be off by 1 somewhere.

There are probably clever ideas which are not O(n), like
splitting the number in two halves and recurse on both, but
I'd have to think hard to code it, so I'll leave this as an
exercise to the reader ;)

If you're on IA32, there's also an insn to compute that.
(Actually, the position of the highest set bit, with which you
probably can deduce log2 easily).

-- 
Vincent Penquerc'h 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.linux.org.au/pipermail/linuxcprogramming/attachments/20021003/91019498/attachment.htm