Home » Interview » Algorithm » Number Of 1 bits

Number Of 1 bits


We have all heard of the Hamming Weight of a binary number. Hamming weight is the number of set bits/1s in a binary number. In this problem Number Of 1 bits we have to find the hamming weight of the given number.

Examples

Number = 3

Binary representation = 011

Hamming weight = 2

Number = 4

Binary representation = 100

Hamming weight = 1

A few image representations are gonna help out more

Number Of 1 bits

Now, let us look into how to find it out

Approach – 1A

Brute Force

The Brute force approach would be

  • Find n%2 to give us the bit at that position
  • Calculate n=n/2 to move to the next bit

Example

Number=5

Number Of 1 bits

Let us look at the code.

JAVA Program 

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         ans=ans+(n%2);
         n=n/2;
     }
     return ans; 
    }
};

C++ Program

public class Solution { 
       // you need to treat n as an unsigned value 
       public int hammingWeight(int n) 
       { 
           int ans=0; 
           while(n!=0) 
           { 
               ans=ans+(n%2); 
               n=n/2; 
           } 
           return and; 
      } 
}

Time complexity = O(n)

Approach – 1B

Brute Force BUT Smarter!

Well, now that we have a simple approach. Let us look more in terms of Bit-Manipulation

First strengthening our game with a few smart points

  • We know that an accepted integer can be maximum 32 bits long
  • a&1=1 1&0=0
READ  Sieve of Eratosthenes

Keeping these things we can loop over 32 and perform an AND operation to find the set bits

JAVA Program for Number Of 1 bits

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;
    }
}

C++ Program for Number Of 1 bits

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
    for(int i=0;i<32;i++)
    {
        ans=ans+(n&1);
        n=n>>1;
    }
    return ans;    
    }
};

Time complexity = O(n)

A lot of approaches we have collected until now are linear. We should surely have in our kitty one smart thing or two to optimize our game. So, looking across I hit upon something gold.

Approach – 2

Brian Kernighan Algorithm

Before getting all erudite and algorithmic let me get you through the process

  • We calculate n-1
  • We and it with n i.e n&(n-1)
    • Thus unset the rightmost bit
  • Keep repeating the above steps until we end up with 0

Let number=5

Binary representation=101

The process illustrated for num=5
The process illustrated for num=5

Optimizations

  • The algorithm goes through as many iterations as the set bits

Looking into the code

Java Program for Number Of 1 bits

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
}

C++ Program for Number Of 1 bits

class Solution 
{
public:
    int hammingWeight(uint32_t n) 
    {
     int ans=0;
     while(n!=0)
     {
         n=n&(n-1);
         ans++;
     }
     return ans; 
    }
};

Analyzing the time complexity

Each integer has log(n) bits and in the worst case we pass through all the bits

Time complexity = Log(n)

Now that we are speeding up how can we miss an approach that takes O(1)

READ  Sliding Window Technique

Introducing

Approach – 3

Using Advanced Operations

Let us assume we have a binary number=11010011

We use bitmasks here namely 0101,0011,00001111,00000000011111111 and 000000000000000001111111111111111 to perform the procedure shown in the picture.

 

Calculating Hamming weight using Bitmask
Calculating Hamming weight using Bitmask

JAVA Program for Number Of 1 bits

public class Solution 
{
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) 
    {
    n = (n & 0x55555555) + (n >>  1 & 0x55555555); // put count of each  2 bits into those  2 bits 
    n = (n & 0x33333333) + (n >>  2 & 0x33333333); // put count of each  4 bits into those  4 bits 
    n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F); // put count of each  8 bits into those  8 bits 
    n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits 
    n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits 
    return n;
    }
}

The time complexity of the above approach and the space complexity both end up as O(1).

Wanna know more than just Binary. Tune in!

References