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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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 The subject line and your description disagree by 1 bit. Take the number 7: its binary representation would be 0111, with 0100 being the highest bit, whereas the smallest power of 2 >= 7 is 8, or 1000 in binary. And how do you want the results? The place value of that highest bit? Or its index?

For the index, how about this: truncate . (/(log 2)) . log . fromIntegral for the place value, just add an exponent function and another cast: (2**) . fromIntegral . truncate . (/(log 2)) . log . fromIntegral If you want the smallest power of 2 >= the integer, just change truncate to ceiling.

Whatever the answer is, I expect it's relevant to Data.IntSet, which uses big-endian patricia trees. - Conal On Dec 3, 2007 8: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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe