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

Don Stewart dons at galois.com
Tue Dec 4 14:51:40 EST 2007

```dpiponi:
> 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)
>     where
>     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.

Awesome. We can use this in Data.Bits, if you've got some QuickChecks
for it.

-- Don
```