Ayan Banerjee
Posted on July 7, 2020
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
Posted on July 7, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.