Count set bits in an integer

Introduction

In this article, we will address the problem of "Counting set bits" or, alternatively, "Counting the number of set bits in an integer". Our approach will begin with a comprehensive understanding of the problem, followed by a brute-force solution, and eventually optimizing it with logical thinking. We hope this problem-solving journey will help boost your critical thinking and programming abilities. Without further ado, let's begin.

Understand the question

The question "Count set bits in an integer" is asking for the number of 1s or set bits in the binary representation of a given integer. The binary representation of an integer is a sequence of 0s and 1s that represent the number in base 2.

For example, the decimal number 7 is represented in binary as 111, which has three set bits. Similarly, the decimal number 10 is represented in binary as 1010, which has two set bits. The task is to count the number of set bits in any given integer.

This task is commonly used in computer science and is often used in programming interview questions to assess a candidate's ability to manipulate bits and perform bitwise operations efficiently.

For instance, let's consider the decimal number 42, which is represented in binary as 101010. In this case, the number of set bits is 3 because there are three 1s in the binary representation. Another example could be the decimal number 255, which is represented in binary as 11111111. In this case, the number of set bits is 8, as there are eight 1s in the binary representation.

Therefore, the task is to write a program that takes an integer as input, converts it to binary, and counts the number of set bits in the binary representation of the integer.

Brute force method

One approach to counting set bits in an integer is the brute force method. In this method, we iterate through all bits of the integer and check if each bit is set or not. If a bit is set, we increment the count. This approach has a time complexity of O(n) where n is the number of bits in the integer.

Algorithm and Pseudocode

Algorithm for the countSetBitsBruteForce method:

Step 1. Start by initialising a count variable to 0.

Step 2. Iterate through all 32 bits of the integer using a for loop.

Step 3. In each iteration, check if the i-th bit of the integer is set or not.

Step 4. If the i-th bit is set, increment the count variable.

Step 5. After iterating through all 32 bits, return the final count value.

Pseudocode:


function countSetBitsBruteForce(n):
    count = 0
    for i from 0 to 31:
        if (n AND (1 << i)) != 0:
            count = count + 1
    return count

In step 3, the expression (1 << i) is a bit shifting operation that shifts the binary digit 1 by i positions to the left. This means that the resulting binary number will have a 1 in the i-th position from the right, and all other bits will be 0.

For example, if i = 3, then (1 << i) would give us the binary number 1000 (which is 8 in decimal). If i = 5, then (1 << i) would give us the binary number 100000 (which is 32 in decimal).
Next, the AND operator is used to perform a bitwise AND operation between the binary representation of n and the binary representation of (1 << i). The result of this operation will be a new binary number that has a 1 in the i-th position if and only if the i-th bit of n is also 1.

How to "get bit" we already covered before, you can click here to get the more detail explanation.

Java code implementation


package codeKatha.dsa;

public class SetBitsCounter {
    public static int countSetBitsBruteForce(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }
}

Code traversal with an example

If we pass n = 5 to the countSetBitsBruteForce method, the method will traverse the code as follows:
  1. count variable is initialized to 0.
  2. A for loop is executed with variable i ranging from 0 to 31 (inclusive).
  3. In each iteration of the loop, the expression 1 << i is evaluated. This shifts the binary representation of 1 i bits to the left. For i = 0, 1 << i evaluates to 1. For i = 1, 1 << i evaluates to 10 (binary representation of 2). For i = 2, 1 << i evaluates to 100 (binary representation of 4). And so on.
  4. The expression n & (1 << i) is evaluated. This performs a bitwise AND operation between n and the binary value obtained from shifting 1 by i bits to the left. For example, for i = 0, n & (1 << i) will be 5 & 1, which evaluates to 1. For i = 1, n & (1 << i) will be 5 & 2, which evaluates to 0. For i = 2, n & (1 << i) will be 5 & 4, which evaluates to 4.
  5. If the result of the expression in step 4 is not equal to 0, it means that the i-th bit in n is set to 1, so the count variable is incremented by 1.
  6. The loop continues until all 32 bits have been checked.
  7. The final value of count (which is 2) is returned by the method.
Therefore, if we call the method with n = 5, it will return the value 2.

Brian Kernighan's algorithm

Brian Kernighan's algorithm uses bitwise AND operation to remove the rightmost set bit from the number in each iteration. This operation sets the rightmost set bit to 0, reducing the number of set bits by 1. We continue this process until the number becomes 0.

Algorithm and Pseudocode

Algoritham for countSetBitsKernighan:

Step 1. Initialize a count variable to 0.

Step 2. Loop while the integer is not zero.

Step 3. In each iteration, increment the count variable and clear the rightmost set bit of the integer.

Step 4. Return the final count value.

Pseudocode:


function countSetBitsKernighan(n):
    count = 0
    while (n != 0):
        count = count + 1
        n = n & (n - 1)
    return count

Java code implementation


package codeKatha.dsa;

public class SetBitsCounter {
    public static int countSetBitsKernighan(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

Code traversal with an example

If we pass n = 5 to the countSetBitsKernighan method, the method will traverse the code as follows:
  1. count variable is initialized to 0.
  2. The while loop condition is evaluated. Since n is not equal to 0, the loop is executed.
  3. count variable is incremented to 1.
  4. The expression n & (n - 1) is evaluated. The value of n - 1 is 4 and the binary representation of n is 101. Therefore, n & (n - 1) will be 101 & 100, which evaluates to 100 (binary representation of 4).
  5. The value of n is updated to 4.
  6. The while loop condition is evaluated again. Since n is not equal to 0, the loop is executed.
  7. count variable is incremented to 2.
  8. The expression n & (n - 1) is evaluated. The value of n - 1 is 3 and the binary representation of n is 100. Therefore, n & (n - 1) will be 100 & 011, which evaluates to 000 (binary representation of 0).
  9. The value of n is updated to 0.
  10. The while loop condition is evaluated again. Since n is now equal to 0, the loop is terminated.
  11. The final value of count (which is 2) is returned by the method.
                    Therefore, if we call the method with n = 5, it will return the value 2.

                    In the above Java code, we have implemented the Brian Kernighan's algorithm to count the number of set bits in an integer. The method countSetBitsKernighan takes an integer as input and returns the number of set bits in the binary representation of the integer. The algorithm has a time complexity of O(log n), where n is the number of bits in the integer, which is much more efficient than the brute force method.

                    Use a precomputed lookup table

                    Another approach to count set bits in an integer is to use a precomputed lookup table. In this approach, we create a lookup table that contains the number of set bits for all possible 8-bit integers. We can then use this lookup table to count the number of set bits in any 32-bit integer by dividing it into 4 8-bit sub-integers and using the lookup table to count the set bits in each sub-integer. The total number of set bits in the 32-bit integer is equal to the sum of set bits in all the 8-bit sub-integers.

                    Algorithm and Pseudocode

                    Algorithm for countSetBitsLookupTable:

                    Step 1. Create a lookup table that contains the number of set bits for all possible 8-bit integers.

                    Step 2. Divide the 32-bit integer into 4 8-bit sub-integers.

                    Step 3. Use the lookup table to count the number of set bits in each sub-integer.

                    Step 4. Sum up the number of set bits in all the 8-bit sub-integers to get the total number of set bits in the 32-bit integer.

                    Pseudocode:

                    
//0xFF is a hexadecimal literal that represents the integer value 255

function countSetBitsLookupTable(n):

    lookupTable = createLookupTable()
    
    count = lookupTable[n & 0xFF] + lookupTable[(n >> 8) & 0xFF] +
            lookupTable[(n >> 16) & 0xFF] + lookupTable[(n >> 24) & 0xFF]
            
    return count

                    Java code implementation

                    
package codeKatha.dsa;

public class SetBitsCounter {
    private static final int[] lookupTable = createLookupTable();

    private static int[] createLookupTable() {
        int[] table = new int[256];
        for (int i = 0; i < 256; i++) {
            int count = 0;
            for (int j = 0; j < 8; j++) {
                if (((i >> j) & 1) == 1) {
                    count++;
                }
            }
            table[i] = count;
        }
        return table;
    }
    
	
     // In Java, 0xFF is a hexadecimal literal that represents the integer value 255 in decimal notation.
     // It is equivalent to the binary value 11111111 which is a byte with all bits set to 1.
     
    public static int countSetBitsLookupTable(int n) {
        int count = lookupTable[n & 0xFF] + lookupTable[(n >> 8) & 0xFF] +
                    lookupTable[(n >> 16) & 0xFF] + lookupTable[(n >> 24) & 0xFF];
        return count;
    }
}

                    Code traversal with an example

                    If we pass n = 5 to the countSetBitsLookupTable method, the method will traverse the code as follows:

                    1. A static lookup table lookupTable is defined and initialized by calling the createLookupTable() method.
                    2. The createLookupTable() method creates an array of size 256 and fills it with the number of set bits in each of the 8-bit values from 0 to 255. It then returns this array as the lookup table.
                    3. The countSetBitsLookupTable method is called with n = 5.
                    4. A count variable is initialized to the sum of the number of set bits in the four 8-bit values of n using the lookup table.
                    5. The first 8 bits of n are extracted by performing a bitwise AND operation between n and the hexadecimal value 0xFF. This is done by looking up the value of lookupTable[n & 0xFF] which gives the number of set bits in the first 8 bits of n.
                    6. The next 8 bits of n are extracted by right-shifting n by 8 bits and then performing a bitwise AND operation with 0xFF. This is done by looking up the value of lookupTable[(n >> 8) & 0xFF] which gives the number of set bits in the second 8 bits of n.
                    7. Steps 5 and 6 are repeated for the next two sets of 8 bits of n to get the total count of set bits in n.
                    8. The final value of count (which is 2) is returned by the method.
                    Therefore, if we call the method with n = 5, it will return the value 2.

                    In the above Java code, we have implemented the precomputed lookup table approach to count the number of set bits in an integer. The method createLookupTable creates a lookup table that contains the number of set bits for all possible 8-bit integers. The method countSetBitsLookupTable takes a 32-bit integer as input, divides it into 4 8-bit sub-integers, and uses the lookup table to count the set bits in each sub-integer. Finally, it sums up the number of set bits in all the 8-bit sub-integers to get the total number of set bits in the 32-bit integer. This approach has a time complexity of O(1) but requires additional memory to store the lookup table.

                    Hope this blog tutorial has been helpful to you. If you have any remaining doubts or suggestions, please feel free to share them in the comments below. We would be glad to receive your feedback.

                    💛 You can Click Here to connect with us. We will give our best for you.

                     ← Bit Manipulation and Bit Masking Concepts
                     
                    List of all chapters of this course
                                          Find the two non-repeating elements in an array of repeating elements (upcoming..) →
                    Related categories:

                    Comments

                    Post a Comment

                    Popular Posts on Code Katha

                    Java Interview Questions for 10 Years Experience

                    Image
                    Welcome to the comprehensive guide on "Java Interview Questions for 10 Years Experience." Java has been one of the most popular programming languages for decades, and its widespread adoption means that the demand for skilled Java developers has never been higher. If you are someone who has been working with Java for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Spring boot interview Questions for 10 years experiance This blog post will provide you with a list of commonly asked interview questions for 10 years experienced Java developers. It will also include detailed answers to each question, with explanations and examples to help you understand the concepts and their practical implementations better. Whether you are preparing for a job interview or just want to brush up your knowl
                    Read more

                    Sql Interview Questions for 10 Years Experience

                    Image
                    As an experienced SQL professional, you might encounter challenging questions during a job interview. In this blog post, we will explore 10 common SQL interview questions and provide in-depth explanations along with relevant examples. Let's dive in! Contents [ hide ] What is SQL Injection, and how can you prevent it? SQL Injection is a malicious attack where an attacker manipulates input data to execute unintended SQL statements. It can lead to unauthorized access, data breaches, and data manipulation. To prevent SQL Injection, follow these best practices: 1.1. Use Prepared Statements: Prepared statements or parameterized queries separate SQL code from data input, preventing attackers from injecting malicious SQL code. Here's an example in PHP: $stmt = $pdo->prepare('SELECT * FROM users WHERE username = :username'); $stmt->bindParam(':username', $username); $stmt->execute(); 1.2. Sanitize User Input: Validate and sanitize user input
                    Read more

                    Spring Boot Interview Questions for 10 Years Experience

                    Image
                    Welcome to the comprehensive guide on "Spring Boot Interview Questions for 10 Years Experience". Spring Boot has become one of the most popular frameworks for developing enterprise-grade applications, and its widespread adoption means that the demand for skilled Spring Boot developers has never been higher. If you are someone who has been working with Spring Boot for the last decade, you have accumulated a wealth of experience and knowledge that you can showcase during interviews. Recommended  to read and brush up for your interview: Must know interview questions and concept for any Java Interview Java Interview Questions for 10 Years Experience This blog post will provide you with a list of commonly asked interview questions for 10 years experienced Spring Boot developers. It will also include detailed answers to each question, with explanations and examples to help you understand the concepts and th
                    Read more

                    Visual Studio Code setup for Java and Spring with GitHub Copilot

                    Image
                    Introduction- In this tutorial blog, we will explore the process of setting up and utilising Visual Studio Code for Java programming, as well as incorporating GitHub Copilot as a valuable coding tool. Visual Studio Code is a powerful and versatile code editor that offers a wide range of features and extensions for Java developers. By using Visual Studio Code for Java programming, developers can benefit from features such as code completion, debugging, and live coding. Additionally, with the integration of GitHub Copilot, developers can streamline their coding process with AI-assisted suggestions for code snippets and functions. This blog will provide a comprehensive guide for setting up and using these tools for Java development. Contents [ hide ] Setup Visual Studio Code for Java and Spring Visual Studio Code (VS Code) is an open-source code editor that supports a wide range of programming languages, including Java. It is a powerful tool
                    Read more

                    Java interview questions - Must to know concepts

                    Contents [ hide ] How does Java achieve platform independence, and what is the underlying principle? Java programs can run on diverse operating systems and hardware setups without requiring modification. This feat is primarily achieved through the concept of the Java Virtual Machine (JVM). The Java Virtual Machine (JVM) The JVM acts as a bridge between the Java code you write and the underlying hardware and operating system . When you compile your Java code, it is translated into an intermediate form called bytecode, which is not tied to any specific platform. The JVM then comes into play. It takes this bytecode and dynamically translates it into machine-specific instructions that the host system can execute. This means that a Java program can be written once and executed on any system with the appropriate JVM for that system. Example: Running a Java Program on Different Platforms Consider a simple Java program that calculates the sum of two numbers: package codeKatha
                    Read more

                    Spring Data JPA

                    Image
                    Introduction- We will learn here Spring Data JPA, perform CRUD operation, Clear concept of Relationship mapping like one-to-many, many-to-one with Example. Spring Data JPA is a powerful framework that simplifies the process of working with relational databases in Java applications. It provides an easy-to-use API for working with JPA, allowing developers to focus on their business logic instead of worrying about the details of how JPA works. With Spring Data JPA, you can easily define entities that map to database tables, and then use them to perform CRUD (create, read, update, delete) operations on those tables. In addition, Spring Data JPA provides support for more advanced features like querying and pagination, making it an excellent choice for both small and large projects. Contents [ hide ] In this blog, we will explore Spring Data JPA by building a sample application that uses it to manage users and packs. But, before let
                    Read more

                    Data Structures & Algorithms Tutorial with Coding Interview Questions

                    Image
                    About the Course This course offers comprehensive coverage of coding questions that serve as a solid foundation for understanding DSA concepts. These questions are frequently asked in coding interviews, either directly or with some variations, by many companies, including Adobe, Facebook (Meta), Paytm, Amazon, Google, and others. Our primary objective is to enhance your problem-solving skills and enable you to devise optimal solutions. The course includes a wide range of topics, such as Arrays, Strings, Searching and Sorting, Greedy Algorithms, Trees, Graphs, Dynamic Programming, and more. Upon completion, you will possess the necessary skills to ace DSA interviews for typical companies or excel in the initial rounds of product-based companies such as Google, Microsoft and similar others. We are started with Graph data Structure and add others soon. Contents [ hide ] Approach Our course is  organised into chapters that foll
                    Read more

                    Elasticsearch Java Spring Boot

                    Image
                    Introduction- In this blog, we will learned how to use Elasticsearch with Spring Boot to build a search application. We will created several classes as an example, including ElasticsearchConfig, Book, BookService, BookController, and BookRepository, to demonstrate how to use Elasticsearch with Spring Boot. After this tutorial, you can start building your own search application using Elasticsearch and Spring Boot. Elasticsearch is a powerful search and analytics engine that can be used to build highly scalable and fault-tolerant applications. In this blog, we will learn how to use Elasticsearch with Spring Boot to build a search application. First we will Set up a Spring Boot project with Elasticsearch after that we will see how to make connection with elasticsearch. Once connection setupt is done then we will add data then perform queries and searching on Elasticsearch. Contents [ hide ] Setting up a Spring Boot project with Elas
                    Read more

                    Java interview questions for 5 years experience

                    Contents [ hide ] What is difference between Heap and Stack Memory in Java, and shed light on their utilization? In Java, memory management plays a crucial role in determining how objects are stored and accessed during program execution . Heap and Stack Memory are two distinct regions where different types of data are managed. Understanding their differences is essential for efficient memory utilisation and managing object lifecycles. Stack Memory Stack Memory is a region used for storing method calls, local variables, and references to objects . It operates in a Last-In-First-Out (LIFO) manner , resembling a stack of items. Each method call creates a new frame in the stack, containing variables specific to that method. Stack Memory is relatively fast for allocation and deallocation because it follows a strict order. However, it has limited space and is typically used for small, short-lived data. Primitive data types and references to objects are often stored here. Ex
                    Read more