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

[Don Stewart]

dpiponi:
> 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.

Well, you could use testBit, which is pretty efficient,

    x `testBit` i       = (x .&. bit i) /= 0
    (J# s1 d1) .&. (J# s2 d2) = 
        case andInteger# s1 d1 s2 d2 of
          (# s, d #) -> J# s d

Of course, working out which bit to test is the puzzle :)

Just for fun, I tried to see how large gmp could go,

    import Data.Bits
    import Text.Printf

    main = mapM_ test [0,100000000 ..]
      where
        test n = printf "2 ^ %d has bit %d set: %s\n" n n (show t)
            where
                t = (2 ^ n :: Integer) `testBit` n

gmp is quite remarkable.

    $ ghc  -O2 A.hs -o A
    $ time ./A  
    2 ^ 0 has bit 0 set: True
    2 ^ 100000000 has bit 100000000 set: True
    2 ^ 200000000 has bit 200000000 set: True
    2 ^ 300000000 has bit 300000000 set: True
    2 ^ 400000000 has bit 400000000 set: True
    2 ^ 500000000 has bit 500000000 set: True
    2 ^ 600000000 has bit 600000000 set: True
    A: out of memory (requested 202375168 bytes)
    ./A  504.00s user 1.73s system 99% cpu 8:26.71 total

and I ran out of ram.

-- Don