Count the number of set bits of an integer.

**Examples:**

Input: 31

Output: 5

Explanation: Binary representation of 31 is 11111

Input: 42

Output: 3

Explanation: Binary representation of 42 is 101010

## Approach-1: Naive

Naive algorithm is to use the binary representation of the number and count the number of set bits.

C++ code:

```
#include<iostream>
using namespace std;
int countSetBits(int n) {
int count = 0;
while (n > 0) {
count += n & 1; // check if the last bit is set
n = n >> 1; // right shift by 1 is equivalent to division by 2
}
return count;
}
int main() {
cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
return 0;
}
```

Python code:

```
def count_set_bits(n):
count = 0
while n > 0:
count += n & 1
n = n >> 1
return count
if __name__ == '__main__':
print('Number of set bits of', 31, 'is', count_set_bits(31))
print('Number of set bits of', 42, 'is', count_set_bits(42))
```

Time Complexity: `O(logN)`

where N is the number

Space Complexity: `O(1)`

as we are not using any extra space

## Approach-2: Brian Kernighan Algorithm

`n = n & (n - 1)`

clears the rightmost set bit. Let us take a look at some

examples.

```
n => 101010
n - 1 => 101001
---------------------
n & (n - 1) => 101000
```

`n`

is updated to `101000`

now.

```
n => 101000
n - 1 => 100111
---------------------
n & (n - 1) => 100000
```

`n`

is updated to `100000`

now.

```
n => 100000
n - 1 => 011111
--------------------------
n & (n - 1) => 000000
```

`n`

is now 0.

Thus, we need only 3 iterations to find the count of set bits.

C++ code:

```
#include<iostream>
using namespace std;
int countSetBits(int n) {
int count = 0;
while (n > 0) {
n = n & (n - 1); // clear the right-most bit
++count;
}
return count;
}
int main() {
cout << "Number of set bits of " << 31 << " is " << countSetBits(31) << "\n";
cout << "Number of set bits of " << 42 << " is " << countSetBits(42) << "\n";
return 0;
}
```

Python code:

```
def count_set_bits(n):
count = 0
while n > 0:
n = n & (n - 1) # clear the right most bit
count += 1
return count
if __name__ == '__main__':
print('Number of set bits of', 31, 'is', count_set_bits(31))
print('Number of set bits of', 42, 'is', count_set_bits(42))
```

Time Complexity: `O(logN)`

when N has all of its bit set

Space Complexity: `O(1)`

as we are not using any extra space

## Discussion (0)