Make delicious recipes!

Count number of ones in binary representation of an integer



Problem: Count number of ones in binary representation of a given integer.
For example, binary representation of 4 is 100 and the number of ones in it is 1.
Similarly, binary representation of 99 is 1100011 and the number of ones in it is 4.


Solution: A naive solution for this problem would be to shift the given integer by 1 and increment a count if the last bit is 1.
However, that would need 'k' iterations of the for loop where k is the position of the last 1.
For example, for 99, the loop would require to execute 7 times.

This can be optimized by using the trick here: Check if a number is power of 2
By making use of the above, below code reduces a single 1 bit from 'n' in each iteration of the loop.
So, the loop iterates only as many times as there are 1s in the integer.

Code:

void countOnes (int n) 
{
    int count=0;
    while (n!=0)
    {
        n = n & (n-1);
        count++;
    }
}

Sample Run for integers from 0 to 100:
00) 0
01) 1
02) 1
03) 2
04) 1
05) 2
06) 2
07) 3
08) 1
09) 2
10) 2
11) 3
12) 2
13) 3
14) 3
15) 4
16) 1
17) 2
18) 2
19) 3
20) 2
21) 3
22) 3
23) 4
24) 2
25) 3
26) 3
27) 4
28) 3
29) 4
30) 4
31) 5
32) 1
33) 2
34) 2
35) 3
36) 2
37) 3
38) 3
39) 4
40) 2
41) 3
42) 3
43) 4
44) 3
45) 4
46) 4
47) 5
48) 2
49) 3
50) 3
51) 4
52) 3
53) 4
54) 4
55) 5
56) 3
57) 4
58) 4
59) 5
60) 4
61) 5
62) 5
63) 6
64) 1
65) 2
66) 2
67) 3
68) 2
69) 3
70) 3
71) 4
72) 2
73) 3
74) 3
75) 4
76) 3
77) 4
78) 4
79) 5
80) 2
81) 3
82) 3
83) 4
84) 3
85) 4
86) 4
87) 5
88) 3
89) 4
90) 4
91) 5
92) 4
93) 5
94) 5
95) 6
96) 2
97) 3
98) 3
99) 4







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal