Counting number of one's in a binay number

Question

how does this code works

for example

input: 5(101)
ouput: 2

the function is

scanf("%d", &a);
while(a)
{
oneina++;
a=a&(a-1);
}
printf("%d", oneina);

Take a pencil and paper and try to figure what `a=a&(a-1)` does. — devnull, May 04 '14 at 05:54
@BurhanKhalid so then what do you think it should do, frankly? It is **entirely obvious** that it should (and does) count the number of ones in the binary representation of a given integer. — The Paramagnetic Croissant, May 04 '14 at 05:59
Err, what? I suppose you're asking *how* the code works? I don't understand the question here. — Cody Gray - on strike, May 04 '14 at 06:00
sorry for my English, I am expecting a solution in the form of a general derivation(for all cases) rather than the explanation of the example... — eightnoteight, May 04 '14 at 08:28

score 1 · Accepted Answer · answered May 04 '14 at 05:58

1

a-1 is a with the first 1 (from right) occurring in a as 0 and all the bits to the right of that bit as 1. So when you bitwise and them, you remove one 1 from a at a time.

answered May 04 '14 at 05:58

HelloWorld123456789

5,299
3
23
33

score 0 · Answer 2 · answered May 04 '14 at 06:27

scanf("%d", &a);      // a = 0111b (7)

while(a)              // a = 0111b (7) : TRUE

   oneina++;          // oneina 0 --> 1

   a=a & (a-1);       // a = 0111b (7) & 0110b (6) = 0110b (6)

while(a)              // a = 0110b (6) : TRUE

   oneina++;          // oneina 1 --> 2

   a=a & (a-1);       // a = 0110b (6) & 0101b (5) = 0100b (4)

while(a)              // a = 0100b (4) : TRUE

   oneina++;          // oneina 2 --> 3

   a=a & (a-1);       // a = 0100b (4) & 0011b (3) = 0000b (0)

while(a)              // a = 0000b (4) : FALSE

printf("%d", oneina); // '3'

Counting number of one's in a binay number

2 Answers2