Programming Praxis - Population Count

In today’s Programming Praxis, our task is to count the active bits in a number. Let’s get started, shall we?

Some imports:

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.

About these ads

Tags: bits, bonsai, code, count, Haskell, kata, population, praxis, programming