<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1252">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2448.0">
<TITLE>RE: [LCP]Base 2 logarithms</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>> What's the best way to calculate base 2 logarithms? I know </FONT>
<BR><FONT SIZE=2>> that I could</FONT>
<BR><FONT SIZE=2>> use log(x)/log(2) or log10(x)/log10(2), but I'm not sure </FONT>
</P>
<P><FONT SIZE=2>Of an int ?</FONT>
<BR><FONT SIZE=2>If not an int, then floor it, and get the int, then:</FONT>
</P>
<P><FONT SIZE=2>unsigned int log2(unsigned int n)</FONT>
<BR><FONT SIZE=2>{</FONT>
<BR><FONT SIZE=2> int l=0;</FONT>
<BR><FONT SIZE=2> while (n) {</FONT>
<BR><FONT SIZE=2> n>>=1;</FONT>
<BR><FONT SIZE=2> ++l;</FONT>
<BR><FONT SIZE=2> }</FONT>
<BR><FONT SIZE=2> return n;</FONT>
<BR><FONT SIZE=2>}</FONT>
</P>
<P><FONT SIZE=2>That's the general idea, I might be off by 1 somewhere.</FONT>
</P>
<P><FONT SIZE=2>There are probably clever ideas which are not O(n), like</FONT>
<BR><FONT SIZE=2>splitting the number in two halves and recurse on both, but</FONT>
<BR><FONT SIZE=2>I'd have to think hard to code it, so I'll leave this as an</FONT>
<BR><FONT SIZE=2>exercise to the reader ;)</FONT>
</P>
<P><FONT SIZE=2>If you're on IA32, there's also an insn to compute that.</FONT>
<BR><FONT SIZE=2>(Actually, the position of the highest set bit, with which you</FONT>
<BR><FONT SIZE=2>probably can deduce log2 easily).</FONT>
</P>
<P><FONT SIZE=2>-- </FONT>
<BR><FONT SIZE=2>Vincent Penquerc'h </FONT>
</P>
</BODY>
</HTML>