[Haskell-cafe] Looking for smallest power of 2 >= Integer
Sterling Clover
s.clover at gmail.com
Tue Dec 4 00:32:43 EST 2007
Actually, I suspect GHC's strictness analyzer will give you
reasonable performance with even the naive version, but fancier ideas
are at http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
The problem with all those, however, is since they do bit-twiddling
and use shifts and masks, they're designed to, as far as I can tell,
only work on integers of defined sizes (the names given to the
functions to the contrary). You could, of course, dynamically choose
how many masks to apply based on the length of the Integer in
question, which can, if all else fails, be determined by unpacking it
into the primitives, which are (# Int#, ByteArr# #) with the Int# as
the number of "limbs" of the integer, as well as its sign. As far as
I understand it, each "limb" is generally 32 bits.
Unless this is a real performance hotspot, you're probably fine
sticking with a relatively naive version. For example, in my
translation of the clean version of the meteor-contest shootout
entry, I used the following function (which, I'll grant, does
something slightly different):
first0 :: Mask -> Int
first0 i
| i .&. 1 == 0 = 0
| otherwise = 1 + first0 (i `shiftR` 1)
and it worked out fine for my purposes.
--s.
On Dec 3, 2007, at 11:36 PM, Dan Piponi wrote:
> Is there anything in any of the interfaces to Integer that will allow
> me to quickly find the highest bit set in an Integer? If not, does
> anyone have any recommendations for how to do it efficiently. There
> are some obvious things that come to mind but which might involve
> quite a bit of useless copying of data internally by the
> implementation of Integer.
> --
> Dan
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
More information about the Haskell-Cafe
mailing list