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
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala