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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
`Number of 1's in the binary representation of 6 is: 2`