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..)

                    Comments

                    Popular Posts on Code Katha

                    Java Interview Questions for 10 Years Experience

                    Sql Interview Questions for 10 Years Experience

                    Spring Boot Interview Questions for 10 Years Experience

                    Java interview questions - Must to know concepts

                    Visual Studio Code setup for Java and Spring with GitHub Copilot

                    Spring Data JPA

                    Data Structures & Algorithms Tutorial with Coding Interview Questions

                    Spring AI with Ollama

                    Java interview questions for 5 years experience

                    Elasticsearch Java Spring Boot