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

• Two Sum Problem
• Add Binary
• Pascal Triangle
• Reverse Words in a String
• Valid Parentheses Problem

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