Probably the simplest version is magic = 0x07EDD5E59A4E28C2 offset = 58 lsbTable :: UArray Word64 Word8 lsbTable = listArray (0, 63) [ 63, 0, 58, 1, 59, 47, 53, 2 , 60, 39, 48, 27, 54, 33, 42, 3 , 61, 51, 37, 40, 49, 18, 28, 20 , 55, 30, 34, 11, 43, 14, 22, 4 , 62, 57, 46, 52, 38, 26, 32, 41 , 50, 36, 17, 19, 29, 10, 13, 21 , 56, 45, 25, 31, 35, 16, 9, 12 , 44, 24, 15, 8, 23, 7, 6, 5 ] foldrBits :: (Int -> a -> a) -> a -> Word64 -> a foldrBits f z 0 = z foldrBits f z n | t <- n .&. negate n = f (fromIntegral (lsbTable ! shiftR (t * magic) offset)) (foldrBits f z (xor n t)) swapping to lsbTable = listArray (0,31) [0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9] magic = 0x077CB531 offset = 27 for the 32 bit case. -Edward