EPI 5.1 - Find the number of bits set in a number (and Parity)

The goal is to find the number of set bits in a number, when converted to binary.

So 4 (dec) -> 100 (bin) – has 1 bit set.

Similarly 7 -> 111 -> 3

The straightforward solution shown below has complexity of O(n) where n is the length of the input ie 8 bits for char, 16 bits for short, and 32 bits for int (ignoring hardware and compiler specific sizes here).

1import Data.Bits
2
3num_set_bits_simple 0 = 0
4num_set_bits_simple x = case x .&. 1 of
5                          1 -> 1 + num_set_bits_simple (x `shiftR` 1)
6                          0 -> num_set_bits_simple (x `shiftR` 1)

Apart from being O(n) this also has the disadvantage of not being tail-call recursive and requires a conditional check in each “iteration”.

A solution that depends is O(s) where is the number of set bits is:

1num_set_bits 0 = 0
2num_set_bits x = 1 + num_set_bits (clear_lowest_set_bit x)

where

1clear_lowest_set_bit x = x .&. (x - 1)

Here x & (x – 1) clears the lowest set bit in a number!