Counting One in Binary Expression

Question

Given a number, find the number of 1 in the number’s binary expression. For example, binary express of 10 is 1010. So the number of 1 in it is 2.

Solution

To solve this, we can check each bit by shifting the bits one by one.

1. 1010 -> check 0
2. 101 -> check 1
3. 10 -> check 0
4. 1 -> check 1

So how to check it? we could use the AND function.

1. 1010 -> check 1010 & 1 = 0
2. 101 -> check 101 & 1 = 1 -> counter + 1
3. 10 -> check 10 & 1 = 0
4. 1 -> check 1 & 1 = 1 -> counter + 1

However, negative number will put this program into infinite loop. For example, shifting -10 (0xFFFFFFF6) several times gives 0xFFFFFFFF. Then shifting 0xFFFFFFFF will give 0xFFFFFFFF and makes infinite loops. Therefore instead of shifting the inputting number, we should shift the comparing number.

1. 1010 -> check 1010 & 1 = 0
2. 1010-> check 1010 & 10 = 1 -> counter + 1
3. 1010 -> check 1010 & 100 = 0
4. 1010 -> check 1010 & 1000 = 1 -> counter + 1