Hi,

Am Sonntag, den 18.09.2011, 17:11 -0400 schrieb Edward Kmett:

> I should have mentioned. This function asumes that the input n is not
> equal to 0.

that is fine, that is in invariant that holds for my bit array.

But I guess we’d need to use CPP magic to separate bitness – my code
uses whatever "Word" means. Or does it work gracefully on 32?

How about adding it to Data.Word (then I don’t feel responsible for
getting it fast and can just use it :-))

You can use a smaller DeBruijn multiplication table to handle 32 bits, but the one that I gave puts the answer in the most significant 6 bits of a 64 bit word, so if you use it with a 32 bit word, they'll be setting bits you don't have and all answers will be 0.

Also, if you don't care about the particular order in which you visit the bits you could store the bits in a different order in the Word(64) than you would if you just set them directly by preshuffling them. I was able to derive the following operations, which move the repeated lookups out of the fold:

magic = 0x07EDD5E59A4E28C2

offset = 58

preshuffleTable :: UArray Int Word8

preshuffleTable = 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]

preshuffle :: Int -> Int

preshuffle n = fromIntegral (preshuffleTable ! n)

setShuffled :: Word64 -> Int -> Word64

setShuffled w n = setBit w (preshuffle n)

testShuffled :: Word64 -> Int -> Bool

testShuffled w n = testBit w (preshuffle n)

clearShuffled :: Word64 -> Int -> Word64

clearShuffled w n = clearBit w (preshuffle n)

-- NB: the bits do not come out in order!

foldShuffledBits :: (Int -> a -> a) -> a -> Word64 -> a

foldShuffledBits f z 0 = z

foldShuffledBits f z n | t <- n .&. negate n = f (fromIntegral (shiftR (t * magic) offset)) (foldShuffledBits f z (xor n t))

unshuffleTable :: UArray Int Word8

unshuffleTable = listArray (0,63)

[1,3,7,15,31,63,62,61,59,54,45,27,55,46,29,58,53,42,21,43,23,47,30,60,57,50,37,11,22,44,25,

51,38,13,26,52,41,18,36,9,19,39,14,28,56,49,34,5,10,20,40,17,35,6,12,24,48,33,2,4,8,16,32,0]

I can derive a similar magic, offset and preShuffle table could be derived for 32 bits, I just haven't needed it.

The caveat is that you'd get the bits out in the wrong order for toAscList, but if you are concerned with the performance of foldBits it may be a win in other areas and you can loop and test shuffled bits for when you really do need the values in ascending order.

-Edward