## Posts Tagged ‘count’

### 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.

### Programming Praxis – Word Count

December 8, 2009

In today’s Programming Praxis exercise, we have to implement the Unix wc command line utility. Let’s get started.

First, we need some imports.

```import System.Environment
import Text.Printf
```

We handle the command line arguments with a bit of pattern matching.

```parseOpts :: [String] -> ([Bool], [String])
parseOpts (('-':ps):args) = (map (`elem` ps) "lwc", args)
parseOpts args            = (replicate 3 True, args)
```

Next, we need to do the actual counting:

```count :: [Bool] -> [(String, String)] -> [String]
count opts = map (\(name, text) -> concat
[printf "%8s" \$ if opt then show . length \$ f text else "-"
| (f, opt) <- zip [lines, words, map return] opts] ++ " " ++ name)
```

And finally, the program itself.

```main :: IO ()
main = do args <- getArgs
let (opts, files) = parseOpts args
mapM_ putStrLn . count opts =<< if null files
then fmap (\x -> [("", x)]) getContents
else fmap (zip files) \$ mapM readFile files
```