This post is completed by 1 user

  • 1
 Add to List
Beginner

224. Number of 1’s in bit representation of a number

Objec­tive:  Write an algorithm to count the number of 1’s in the bit representation of a given number.

Exam­ple:

Number: 6
Output: 2 ( 1 1 0)

Number: 11
Output: 3 ( 1 0 1 1)

 Approach:
Method 1:

  1. While number > 0
  2. Keep doing the number & 1, increment count if the result is 1
  3. Do the right shift

Method 2:

  1. While number > 0
  2. Keep doing the number MOD 2, increment count if the result is 1
  3. Divide the number by 2.

Method 3: Brian Kernighan’s Algorithm

  1. While number > 0
  2. Increment the count.
  3. Keep doing the number & number –1.

Example:

n = 6
count = 1
Bit representation: 1 1 0
n-1 = 5 => 1 0 1
n = n & n-1 => 1 1 0 & 1 0 1 => 1 0 0
Now n = 4
Count = 2
Bit representation: 1 0 0
n-1 = 3
n = n & n-1 => 1 0 0 & 0 1 1 => 0

Output:

Number of 1's in the binary representation of 6 is: 2

Related Problems: