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).
import Data.Bits num_set_bits_simple 0 = 0 num_set_bits_simple x = case x .&. 1 of 1 -> 1 + num_set_bits_simple (x `shiftR` 1) 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:
num_set_bits 0 = 0 num_set_bits x = 1 + num_set_bits (clear_lowest_set_bit x)
clear_lowest_set_bit x = x .&. (x - 1)
Here x & (x – 1) clears the lowest set bit in a number!