<br><div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> {-# LANGUAGE MagicHash #-}<br> import GHC.Exts<br> import Data.Bits<br> <br> -- experiment with using a LUT here (hint: FFI + static arrays in C)<br>
 ilog2i0, ilog2i1, ilog2i2, ilog2i3, ilog2i4 :: Int -&gt; Int -&gt; Int<br> ilog2i0 k x | x .&amp;. 0xFFFF0000 /= 0 = ilog2i1 (k + 16) (x `shiftR` 16)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i1 k x<br> ilog2i1 k x | x .&amp;. 0xFF00 /= 0&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i2 (k + 8)&nbsp;&nbsp;(x `shiftR` 8)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i2 k x<br> ilog2i2 k x | x .&amp;. 0xF0 /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i3 (k + 4)&nbsp;&nbsp;(x `shiftR` 4)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i3 k x<br> ilog2i3 k x | x .&amp;. 0xC /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;= ilog2i4 (k + 2)&nbsp;&nbsp;(x `shiftR` 2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i4 k x<br> ilog2i4 k x | x .&amp;. 0x2 /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;= k + 1 + (x `shiftR` 1)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = k + x<br> <br> log2i :: Integer -&gt; Int&nbsp;&nbsp;-- actually returns bit length, and returns garbage on negatives, but do you care?<br>
 log2i (J# len adr) = ilog2i0 0 (I# (indexIntArray# adr (len -# 1#))) + I# (32# *# (len -# 1#))<br> log2i (S# sml) = ilog2i0 0 (I# sml)<br> <br></blockquote></div><br>I tried the above but I got wrong results on 2^31..2^32-1 because in the additions in ilog2i4, the number x was -1 because of sign extension performed by the shifts all the way (thanks for the ghci debugger). (So, yes, I do care somewhat about garbage on negatives :)<br>
<br>I modified to the following hoping also to use both on 32 and 64 bit machines. Have I shot myself in the foot anyway? For example, is there a guarantee that the most significant limb is non-zero? Is there any possibility of this or some related function being added to Data.Bits?<br>
<br>{-# LANGUAGE MagicHash #-}<br>import GHC.Exts<br>import Data.Bits<br><br>limbSize = bitSize (0 :: Int)<br><br>ilog2 k x = case limbSize of<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 64 -&gt; ilog2i0 k (fromIntegral x)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 32 -&gt; ilog2i1 k (fromIntegral x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; _ -&gt; undefined<br><br>-- experiment with using a LUT here (hint: FFI + static arrays in C)<br>ilog2i0, ilog2i1, ilog2i2, ilog2i3, ilog2i4, ilog2i5 :: Int -&gt; Word -&gt; Int<br>ilog2i0 k x | x .&amp;. 0xFFFFFFFF00000000 /= 0 = ilog2i1 (k + 32) (x `shiftR` 32)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i1 k x<br>ilog2i1 k x | x .&amp;. 0xFFFF0000 /= 0 = ilog2i2 (k + 16) (x `shiftR` 16)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i2 k x<br>ilog2i2 k x | x .&amp;. 0xFF00 /= 0&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i3 (k + 8)&nbsp; (x `shiftR` 8)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i3 k x<br>ilog2i3 k x | x .&amp;. 0xF0 /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i4 (k + 4)&nbsp; (x `shiftR` 4)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i4 k x<br>ilog2i4 k x | x .&amp;. 0xC /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i5 (k + 2)&nbsp; (x `shiftR` 2)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = ilog2i5 k x<br>ilog2i5 k x | x .&amp;. 0x2 /= 0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = k + 1 + fromIntegral (x `shiftR` 1)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = k + fromIntegral x<br><br>log2i :: Integer -&gt; Int&nbsp; -- actually returns bit length<br>
log2i (J# len adr) = ilog2 0 (I# (indexIntArray# adr (len -# 1#))) + I# (32# *# (len -# 1#))<br>log2i (S# sml) = ilog2 0 (I# sml)<br><br>