[Haskell-cafe] Looking for smallest power of 2 >= Integer

[Steven Fodstad]

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.