You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 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
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.