Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
x = 5
101 5
100 5-1
------
100 4
011 4-1
------
000 0
count of bit 1 == 2
---------------------------------
x = 10
1010 10
1001 10-1
------
1000 9
0111 9-1
------
0000 0
count of bit 1 == 2
---------------------------------
111010
111001
--------
111000
110111
--------
110000
101111
--------
100000
011111
--------
000000 0
count of bit 1 == 4
I think it is more like %. Do "i++" until the highest bit of the num is encountered. We get the rest of bits of the num.
That's pretty simple. Each time you do X &= X-1 it erases the lowest non-zero bit. You repeat it and it removes one bit at a time, until all bits are gone. So that gives you the answer how many bits existed in the original integer.
- Anthony Mai October 02, 2014For example, if the lowest bit is 1, after subtracting 1 it becomes 0. So AND the 1 bit and the 0 bit gives you 0, the bit is removed. All other bits are intact.
Next if you have the lowest bits as 100, subtracting 1 gives 011. AND them together, the lowest three bits cancel out. So that removes another lowest bit, with other bits intact.
Pretty useful trick to quickly count all bits without using if/else.