## Posts Tagged ‘bits’

### Programming Praxis – Population Count

January 28, 2011

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.