## Microsoft Interview Question

Software Engineer / Developers**Country:**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.