Interview Series: Count total set bits in all numbers from 1 to n

The way to solve these sorts of problems is to write out the first few values, and look for a pattern

Number  binary   # bits set   F(n)
1       0001     1            1
2       0010     1            2
3       0011     2            4
4       0100     1            5
5       0101     2            7
6       0110     2            9
7       0111     3            12
8       1000     1            13
9       1001     2            15
10      1010     2            17
11      1011     3            20
12      1100     2            22
13      1101     3            25
14      1110     3            28
15      1111     4            32

The Common Solution:

public static int countbits(int num){
   return Integer.bitCount(num);
}

Explanation inner working:
Please find below implementation of the function

public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
}