[Haskell-cafe] Looking for smallest power of 2 >= Integer
Steven Fodstad
flarelocke at hotpop.com
Tue Dec 4 12:21:43 EST 2007
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.
More information about the Haskell-Cafe
mailing list