Count Set Bits Editorial

Practice Problem Link: Count Set Bits

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a positive integer n, count the number of set bits in the binary representation of n.

Approach

The approach to counting the number of set bits in a number is to keep dividing the number by 2 and check if its remainder modulo 2 is equal to 1 or not. We continue this process until the number becomes 0. 

Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Implementation

C++

int countSetBits(int n) {
	int count = 0;
    while(n != 0) {
		count += (n % 2);
		n /= 2;
	}
	return count;
}

Java

class Solution {
    int countSetBits(int n) {
		int count = 0;
		while(n != 0) {
			count += (n % 2);
			n /= 2;
		}
		return count;
    }
}

Alternative Approach

We can use bitwise operators to speed up the average time complexity of the algorithm. We can check if each bit of the number is set by taking its bitwise & with 2ⁱ and checking if it is 1, and counting it.

Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Implementation

C++

int countSetBits(int n) {
	int count = 0;
    for(int i = 0; i < 31; i++) {
		if((1 << i) & n) {
			count++;
		}
	}
	return count;
}

Java

class Solution {
    int countSetBits(int n) {
		int count = 0;
		for(int i = 0; i < 31; i++) {
			if((int)(n & (1 << i)) != 0) {
				count++;
			}
		}
		return count;
    }
}