# Solution Review: Count Set Bits Or Number of 1 bit's

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm. This is a faster execution than the previous naive approach.

## Table of Contents

This review provides a detailed analysis to solve the count set bits.

## Solution review

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm.

## Brian Kernighan’s algorithm

This is a faster execution than the previous naive approach.

In this approach, we count only the set bits. So,

- The while loop runs twice if a number has 2 set bits.
- The while loop runs four times if a number has 4 set bits.

For example, let us consider the example `n = 125`

and calculate using this algorithm.

### Java

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

### Python

```
def CountSetBits(n):
count=0
while n > 0:
n &= (n - 1)
count+=1
return count
number=125
print('SetBit Count is : ', CountSetBits(number))
```

### JavaScript

```
const CountSetBits = (n) => {
let count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
console.log ('SetBit Count is', CountSetBits (125));
```

### C++

```
#include <iostream>
using namespace std;
int helper(int n){
int count = 0;
while (n > 0){
n &= (n - 1);
count++;
}
return count;
}
int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
}
```

### TypeScript

```
export const CountSetBits = (n: number): number => {
let count: number = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
console.log('SetBit Count is', CountSetBits(125));
```

### Explanation

```
n = 40 => 00000000 00000000 00000000 00101000
n - 1 = 39 => 00000000 00000000 00000000 00100111
-----------------------------------------------------------
(n & (n - 1)) = 32 => 00000000 00000000 00000000 00100000
-----------------------------------------------------------
```

Now n is 32, so we can calculate this to:

```
n = 32 => 00000000 00000000 00000000 00100000
n - 1 = 31 => 00000000 00000000 00000000 00011111
-----------------------------------------------------------
(n & (n - 1)) = 0 => 00000000 00000000 00000000 00000000
-----------------------------------------------------------
```

### Time and space complexities

**Time complexity: O(Set Bit count) / O(1) in simple terms**

The time taken is proportional to set bits in binary representation.

So, the time taken is O(SetBit Count).

The run time depends on the number of set 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

or *O*(32)`O(1)`

.

**Space complexity: O(1) extra space**

The space complexity is

. No additional space is allocated.*O*(1)

## Lookup table approach

This approach is considered one of the fastest, using a lookup table.

### Why is the below algorithm faster than previous approaches?

- Lookup-based approach.
- This approach requires a
`O(1)`

time solution to count the set bits. - However, this requires some preprocessing.
- So, we divide our 32-bit input into 8-bit chunks, with four chunks.
- We have 8 bits in each chunk. Then the range is from
`0 - 255`

(0 to 2^{7}). - So, we may need to count set bits from
`o`

to`255`

in individual chunks.

### Java

```
class CountSetBit {
private static int helper(int n) {
int[] table = new int[256];
table[0] = 0;
for (int i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
int res = 0;
for (int i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
public static void main(String[] args) {
int number = 125;
System.out.println("SetBit Count is : " + helper(number));
}
}
```

### Python

```
def CountSetBits(n):
table = [0] * 256
table[0] = 0
for i in range(1, 256):
table[i] = (i & 1) + table[i >> 1]
res = 0
for i in range(4):
res += table[n & 0xff]
n >>= 8
return res
n=125
print ('SetBit Count is', CountSetBits (n))
```

### JavaScript

```
const CountSetBits = (n) => {
const table = [];
table[0] = 0;
for(let i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
let res = 0;
for (let i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
console.log ('SetBit Count is', CountSetBits (125));
```

### C++

```
#include <iostream>
using namespace std;
int helper(int n){
int table[256];
table[0] = 0;
for (int i = 1; i < 256; i++){
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
int res = 0;
for (int i = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
int main() {
int number = 125;
cout << "SetBit count is : " << helper(number);
return 0;
}
```

### TypeScript

```
export const CountSetBits = (n: number): number => {
const table: number[] = [];
table[0] = 0;
for (let i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
let res: number = 0;
for (let i: number = 0; i < 4; i++) {
res += table[n & 0xff];
n >>= 8;
}
return res;
}
console.log('SetBit Count is', CountSetBits(125));
```

### Explanation

In the code snippet below, we store the set bit count value in the lookup table.

```
table[0] = 0;
for (i = 1; i < 256; i++) {
table[i] = (i & 1) + table[i >> 1]; // i >> 1 equals to i/2
}
```

We are initializing the table with the set bit count for each `i`

^{th} place.

### Algorithm:

- Initialize
`table[0]`

with`0`

. - Loop through, in the range from 1 to 256
- for
`i = 1`

,`table[1] = (1&1) + table[1/2]`

=>`table[1] = 1 + table[0]`

=>`table[1] = 1.`

`table[2] = (2&1) + table[2/2]`

=>`table[2] = 0 + table[1];`

=>`table[2] = 1`

.`table[3] = (3&1) + table[3/2]`

=>`table[3] = 1 + table[1];`

=>`table[3] = 2`

. so on…

- Initialize int res = 0.
- Loop through, in the range from 0 to 3
- To check on each of the 4
`8-bit`

chunks using`res += table[n & 0xff]`

; - Shift
`n`

by 8 bits (`n >>= 8`

). we do this to get the second last 8 bits… - End loop.

- To check on each of the 4
- Return
`res`

.

### Time and space complexities

**Time complexity: O(1) in simple terms**

This requires an

time solution to count the set bits in each of the 8-bit chunks.*O*(1)

**Space complexity: O(1) extra space**

The space complexity is

. No additional space is allocated.*O*(1)

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.