### 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:**

- count variable is initialized to 0.
- A for loop is executed with variable i ranging from 0 to 31 (inclusive).
- 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.
- 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.
- 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.
- The loop continues until all 32 bits have been checked.
- The final value of count (which is 2) is returned by the method.

## 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:**

- count variable is initialized to 0.
- The while loop condition is evaluated. Since n is not equal to 0, the loop is executed.
- count variable is incremented to 1.
- 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).
- The value of n is updated to 4.
- The while loop condition is evaluated again. Since n is not equal to 0, the loop is executed.
- count variable is incremented to 2.
- 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).
- The value of n is updated to 0.
- The while loop condition is evaluated again. Since n is now equal to 0, the loop is terminated.
- The final value of count (which is 2) is returned by the method.

**.**

**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:**

- A static lookup table lookupTable is defined and initialized by calling the createLookupTable() method.
- 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.
- The countSetBitsLookupTable method is called with n = 5.
- 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.
- 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.
- 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.
- 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.
- The final value of count (which is 2) is returned by the method.

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

## Post a Comment