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