Home » Technical Interview Questions » Counting Bits

Counting Bits


All about Counting Bits!

Humans have a problem communicating with the computers they made.

Why?

Humans speak and understand the language they have come to speak and listen to over the years but they taught the poor computer 0’s and 1’s.

So today, Let’s teach our computer to count the number of 1’s in a number which is our problem statement( for Counting Bits ).

Given: An integer num which can be any positive integer

What are we supposed to do?

Find out the number of ones in each number from 1 to num. Print the answer in a single line.

Approach Using Simple Bit Manipulation for Counting Bits

Let’s work through a few Bit operations before getting into the details

“>>” this denotes the right shift operator.

“&”    this denotes the AND operator.

Now, see some examples before moving to counting bits.

Let a=1001

a>>1=100

a&1=1

It can also be said that whenever we shift a number right by one unit we divide it by two.

When b=100100

b>>1=10010

Which will already be contained and stored at b/2 in the array

b&1=0

This operation helps us to find whether the last bit is 1 or 0

c=1

c>>1=0

c&1=1

Thus for every number num, the number of 1’s = number of ones in (num/2)+(num&1)

Implementation

Java Program For Counting Bits

class Solution 
{
    public int[] countBits(int num) 
    {
    int a[]=new int[num+1];
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;
    }
}

C++  Program For Counting Bits

class Solution 
{
public:
    vector<int> countBits(int num) 
    {
    vector<int>a(num+1);
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;    
    }
};

8
13

Complexity Analysis

The time complexity of the above approach = O(n)

READ  Core Java Interview Questions

The space complexity of the above approach = O(n) where n is the value which gives us in the input.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup