Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Number of 1’s in bit representation of a number

Objec­tive:  Write an algo­rithm to count the num­ber of 1’s in the bit rep­re­sen­ta­tion 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 num­ber > 0
  2. Keep doing the num­ber & 1, incre­ment count if result is 1
  3. Do the right shift

Method 2:

  1. While num­ber > 0
  2. Keep doing the num­ber MOD 2, incre­ment count if result is 1
  3. Divide the num­ber by 2.

Method 3: Brian Kernighan’s Algorithm

  1. While num­ber > 0
  2. Incre­ment the count.
  3. Keep doing the num­ber & num­ber –1.

Exam­ple:

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

Com­plete Code:

Out­put:

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

You may also like...