[Haskell-cafe] Looking for largest power of 2 <= Integer

Dan Piponi dpiponi at gmail.com
Tue Dec 4 13:48:03 EST 2007

On Dec 3, 2007 10:05 PM, David Benbennick <dbenbenn at gmail.com> wrote:

> Could you please post your code here when you're done?  I'd be
> interested to see the final result.

This is just experimental code I'm playing with in order to implement
exact real arithmetic, so there'll never be a "final" result :-) But
this is what I'm currently playing with. It's hard-coded for a
platform with 64 bit Ints and 64 bit "limbs" of Integers. This is my
first ever foray into the binary underbelly of Haskell, using
information from
and I've probably written this code really stupidly.

import GHC.Exts
import Data.Bits

fastTestBit :: Integer -> Int -> Bool
fastTestBit n i = case n of
    S# m -> testBit (I# m) i
    J# l d -> let I# w = shiftR i 6
                  b = i .&. 63
               in testBit (I# (indexIntArray# d w)) b

-- Assumes n/=0
topBit :: Integer -> Int
topBit n = case n of
    S# m -> topBit' n 63
    J# l _ -> topBit' n (64*I# l-1)
    topBit' n i = if fastTestBit n i then i else topBit' n (i-1)

I don't need something super-fast (ie. clever bit twiddling tricks),
just something not stupidly slow. Despite what dons says, testBit is
stupidly slow :-) fastTestbit takes microseconds instead of seconds on
2^10000000. Maybe a portable tidied up version of fastTestBit ought to
go into Data.Bits. These kinds of operations are ubiquitous in
numerical algorithms.

And note the fixed title :-)

More information about the Haskell-Cafe mailing list