Bit Manipulation

Number of 1’s in bit representation of a number

by

Objec­tive:  Write an algorithm to count the number of 1’s in the bit representation in 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 result is 1
  3. Do the right shift

Method 2:

  1. While number > 0
  2. Keep doing the number MOD 2, increment count if 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

Complete Code:
https://gist.github.com/thmain/96efd526ea3fc7d722be89dfee047f8c

Output:

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

Related Posts: