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 Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala