In today’s Programming Praxis, our task is to count the active bits in a number. Let’s get started, shall we?
import Data.Bits import Data.Word import qualified Data.IntMap as I
We’ll be implementing three different versions. The first is the trivial naive one: go through all the bits and count how many are active. It works for positive and negative numbers of 32 bits or less.
popCount1 :: Bits a => a -> Int popCount1 n = length $ filter (testBit n) [0..31]
Next is Wegner’s algorithm, which works best on sparse bit strings. It works on positive and negative numbers of any length.
popCount2 :: Bits a => a -> Int popCount2 = length . takeWhile (/= 0) . iterate (\n -> n .&. (n - 1))
Finally, there’s the lookup table version, which is faster on large numbers. Unfortunately, it doesn’t handle negative numbers.
popCount3 :: (Integral a, Bits a) => Int -> a -> Int popCount3 k = sum . map ((ps I.!) . fromIntegral . (.&. (2^k - 1))) . takeWhile (/= 0) . iterate (\n -> shiftR n k) where ps = I.fromList $ map (\i -> (i, popCount2 i)) [0..2^k - 1]
Some unit tests to see if everything is working properly:
main :: IO () main = do print $ popCount1 (23 :: Int) == 4 print $ popCount1 (-4 :: Int) == 30 print $ popCount1 (5 :: Word8) == 2 print $ popCount2 (23 :: Int) == 4 print $ popCount2 (-4 :: Int) == 30 print $ popCount2 (5 :: Word8) == 2 print $ popCount2 (2^200000 - 1 :: Integer) == 200000 print $ popCount3 1 (23 :: Int) == 4 print $ popCount3 8 (5 :: Word8) == 2 print $ popCount3 16 (2^200000 - 1 :: Integer) == 200000
Yep. Though unless you’re going to be working with very large numbers I’d recommend using the second version.