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: , , , , , , , ,

One Response to “Programming Praxis – Population Count”

  1. John | Retro Programming Says:

    I’m a fan of the O(log n) parallel bit count. It’s such a shame the code is ugly :-( There’s an example in Forth here http://bit.ly/gSbs4h :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: