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)

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

References