Problem Statement

Given an integer number, count how many set bits (1 bits) are present in its binary representation.

Input:

• number: A non-negative integer.

Output:

• Return the count of set bits.

Constraints:

• 0 ≤ number ≤ 2^31 - 1 (32-bit unsigned integer)

Examples

Example 1:

Input: number = 13 (Binary: 1101)
Output: 3

Explanation: The binary representation of 13 is 1101, which contains three set bits (1s).

Example 2:

Input: number = 8 (Binary: 1000)
Output: 1

Explanation:
The binary representation of 8 is 1000, which contains one set bit.

Different Approaches

1️⃣ Right Shift & Check

Intuition:

You can count the number of set bits by repeatedly checking the least significant bit (rightmost bit). Use a mask (number & 1) to check if the last bit is set and then right-shift the number to check the next bit.

Steps:

1. Initialize a variable count to 0.
2. While the number is greater than 0:
   • If the last bit is set (number & 1), increment count.
   • Right shift the number by 1 (number >> 1) to check the next bit.
3. Return count after all bits are processed.

Code:

#include <iostream>
using namespace std;

int countSetBits(int number) {
    int count = 0;
    while (number > 0) {
        if (number & 1) {  // Check if the last bit is 1
            count++;
        }
        number >>= 1;  // Right shift the number by 1
    }
    return count;
}

int main() {
    int number;
    cout << "Enter the number: ";
    cin >> number;
    cout << "Number of set bits: " << countSetBits(number) << endl;
    return 0;
}

Explanation:

• number & 1: Checks if the least significant bit (LSB) is 1.
• number >>= 1: Right shifts the number to examine the next bit.

Complexity Analysis:

• Time Complexity:O(log N), where N is the value of the number (shifting by 1 in each iteration).
• Space Complexity:O(1)

2️⃣ Brian Kernighan's Algorithm

Brian Kernighan's algorithm is an optimized solution that set bits by repeatedly flipping the rightmost set bit. The idea is to only consider the set bits of an integer by turning off its rightmost set bit, so the next iteration of the loop considers the next rightmost bit.

The expression n & (n-1) can be used to turn off the rightmost set bit of a number n. This works as the expression n - 1 flips all the bits after the rightmost set bit of n, including the rightmost set bit itself. Therefore n & (n-1) results in the last bit flipped of n.

Intuition:

This algorithm is more efficient. The key observation is that if you subtract 1 from a number, the rightmost set bit becomes 0, and all bits to the right of it are flipped. Thus, by repeatedly performing number = number & (number - 1), you can clear the rightmost set bit until the number becomes 0. The number of such operations equals the number of set bits.

Steps:

1. Initialize count = 0.
2. While number > 0:
   • Increment count.
   • Set number = number & (number - 1) (this clears the rightmost set bit).
3. Return count.

Dry Run:

For example, consider the number 10, which is 1010 in binary representation and has a total of 2 bits set.

1st iteration of the loop: n = 10
1010 (n)
&
1001 (n-1)
~~~~~~~~~~~
1000
~~~~~~~~~~~

2nd iteration of the loop: n = 8
1000 (n)
&
0111 (n-1)
~~~~~~~~~~~
0000

Code:

#include <iostream>
using namespace std;

int countSetBits(int number) {
    int count = 0;
    while (number > 0) {
        number = number & (number - 1);  // Clear the rightmost set bit
        count++;
    }
    return count;
}

int main() {
    int number;
    cout << "Enter the number: ";
    cin >> number;
    cout << "Number of set bits: " << countSetBits(number) << endl;
    return 0;
}

Explanation:

• number = number & (number - 1): Clears the rightmost set bit.
• Repeat until number becomes 0.

Complexity Analysis:

• Time Complexity:O(number of set bits), which is much faster than O(log N) when the number has fewer set bits.
• Space Complexity:O(1)

3️⃣ Using GCC built-in function

GCC also provides a built-in function int __builtin_popcount(unsigned int n) that returns the total number of set bits in n.

#include <iostream>
using namespace std;
 
int main()
{
    int n = 10;
    cout << "The total number of set bits in " << n << " is "
         << __builtin_popcount (n) << endl;
 
    return 0;
}

// Output
The total number of set bits in 10 is 2

Complexity Analysis:

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