### How to Count Set Bits in a number - The Coding Shala

Home >> Interview Questions >> counting bits

Please leave a comment below if you like this post or found some error, it will help me to improve my content.

# How to Count Set Bits in a Number

In this post, you will learn how to count set bits or numbers of 1's in a given number. We will implement counting bits solution in Java.

Given a non-negative integer number. For every number, i in the range 0 = i = num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2

Output: [0,1,1]

Example 2:

Input: 5

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

## Counting Bits Java Solution

**Approach 1:**

Using Java's bitCount() method.

Java Program:

class Solution { public int[] countBits(int num) { int[] ans = new int[num+1]; for(int i=0;i<=num;i++){ ans[i] = Integer.bitCount((Integer)i); } return ans; } }

**Approach 2:**

Let's denote the number as num. If it is even, the ending bit is 0, then that bit can be ignored, countBits(num) is the same as countBits(num >> 1), so countBits(num) = countBits(num >> 1). For example:

num: 101010101010

num >> 1: 10101010101

If it is odd, the ending bit is 1, then the number of set bits is that of num - 1 + 1, i.e. countBits(num) = countBits(num - 1) + 1

For example:

num: 101010101011

num - 1: 101010101010

Java Program:

class Solution { public int[] countBits(int num) { int[] bits = new int[num+1]; for(int i=1;i<=num;i++){ if((i&1)==0){ bits[i] = bits[i>>1]; }else{ bits[i] = bits[i-1]+1; } } return bits; } }

**Other Posts You May Like**Please leave a comment below if you like this post or found some error, it will help me to improve my content.

## Comments

## Post a Comment