Counting Bits II

Introduction

This is an extension of the previous counting set bits problem.

Problem Statement

Write a program to return an array of number of 1’s in the binary representation of every number in the range [0, n].

Input: n = 6

Output: [0, 1, 1, 2, 1, 2, 2]

Explanation: 
0 --> 0
1 --> 1
2 --> 1
3 --> 2
4 --> 1
5 --> 2
6 --> 2

Solution

This is a faster execution as we use Brian Kernighan’s algorithm.

In this approach, we count only the set bits. So,

If a number has 2 set bits, then the while loop runs two times.

If a number has 4 set bits, then the while loop runs four times.

Algorithm

Steps:

• Outer loop runs for (n+1) time to store the number of 1 bits present every number from 0 to (n+1).
• Inner loop uses Brian Kernighan’s algorithm to find the number of 1's present in each number

Code