Objective: Write an algorithm to count the number of 1’s in the bit representation in given number.
Example:
Number: 6 Output: 2 ( 1 1 0) Number: 11 Output: 3 ( 1 0 1 1)
Approach:
Method 1:
- While number > 0
- Keep doing the number & 1, increment count if result is 1
- Do the right shift
Method 2:
- While number > 0
- Keep doing the number MOD 2, increment count if result is 1
- Divide the number by 2.
Method 3: Brian Kernighan’s Algorithm
- While number > 0
- Increment the count.
- 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:
Output:
Number of 1's in the binary representation of 6 is: 2