# Counting Bits II

This is an extension to the previous problem counting the number of set bits or 1's present in a number.

We'll cover the following

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.