The Hamming weight of a given binary number is the number of 1s in that number. For example, the number (101)2 has a weight of 2, because its binary representation has two 1s in it. To make the concept crystal clear, we list other examples below of some integers (both decimal and binary representations) with their associated Hamming weights in the following table

Decimal Representation	Binary Representation	Hamming Weight
11	1011	3
156	10011100	4
5623	1010111110111	10

Many methods exist in the literature for computing Hamming weight of a given number. You may consult Wikipedia for efficient software implementations.

However, in this assignment, we do not care much about performance. Instead, we want this assignment to be an opportunity for practicing non-leaf function, especially recursive functions. Therefore, we have implemented a recursive calculator of Hamming weight calculator as shown in the following C code snippet:

int hamming_weight(int x, int li, int ri)

{

int MASK;

int right_count, mid_count, left_count; int delta_index;

if (li

}

else if (li==ri) { MASK = 1<

return ((x & MASK)>>li);

} else {

// divide into three smaller problems delta_index = (li-ri+1)/3; // integer division

left_count = hamming_weight(x, li, li-delta_index );

mid_count = hamming_weight(x, li-delta_index-1, li-2*delta_index); right_count = hamming_weight(x, li-2*delta_index-1, ri);

return right_count + mid_count + left_count;

}

}