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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
