Search⌘ K
AI Features
Home
Courses
Grokking Bit Manipulation for Coding Interviews

Challenge 1: Count Set Bits

Explore how to count set bits in an integer by applying the bitwise AND operator. Understand the binary representation of numbers and implement efficient solutions with bit manipulation. This lesson helps you develop skills to optimize code performance while solving common coding interview challenges.

We'll cover the following...

Introduction

Let’s see how we can count the set bits using the AND operator.

What are set-bits?

1 = set-bit

0 = unset-bit

For example:

Input: 5

Output: 0101 (in binary)

There are two set bits are two in the above example, as we have two 1’s in the binary representation.

Problem statement

Write a program to count set bits of an integer.

Input: 125

Output: 6

Explanation: Input has six 1’s or set-bits so the output will be 6.

Basic solution

In this program, a while-loop is iterated until the expression number > 0 is evaluated to 0 (false).

Let’s see the iterations for number = 125.

Iterations

  • After the first iteration, number(125) will be divided by 2, its value will be 62, and the count incremented to 1.

  • After the second iteration, the value of number(62) will be 31 and, the count incremented to 2.

  • After the third iteration, the value of number(31) will be 15, and the count incremented to 3.

  • And so on.

Then the expression is evaluated to false since the number is 0, and the loop terminates.

number number = number2\frac{number}{2} Set/unSet (1/0) setbit count
125 62 1 1
62 31 0 1
31 15 1 2
15 7 1 3
7 3 1 4
3 1 1 5
1 0 1 6

Code

class CountSetBit {
    private static int helper(int n) {
        int ans = 0;
        while (n > 0) {
            if (n % 2 != 0) {
                ans++;
            }
            n /= 2;
        }
        return ans;
    }
    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

We can further rewrite this code using the & operator as seen below.

public class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

This can be further simplified as shown below:

public class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            count += (n & 1);
            n >>= 1;
        }
        return count;
    }
       
    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

Time and space complexities

Time complexity: O(Total bits in n) / O(1) in simple terms

The time taken is proportional to the total bits in binary representation, which means

int takes 32 bits => O(32 bits) time.

long takes 64 bits => O(64 bits) time.

So, time taken is O(Total bits in n, which can be an int or long, etc.).

The run time depends on the number of bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is O(32) or O(1).

Space complexity: O(1) extra space

The space complexity is O(1)O(1). No extra space is allocated.

Coding exercise

Now, try to optimize the above snippets. There is a better way to solve this problem.

First, take a close look at these code snippets above and think of a better solution. This problem is designed for practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

class Solution{
    public static int countSetBits(int n){
         // Write - Your - Code- Here
        
        return -1; // change this and return the correct setbit count
    }
}

The solution will be explained in the next lesson.