You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Counting One in Binary Expression

Nicholas Wong
Nicholas Wong

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.