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

Home >> Interview Questions >> counting bits

# 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