Count Set Bits in an Integer

71
0

Given a non-negative integer n, find the total number of 1s in its binary representation. Each binary digit equal to 1 is called a set bit.

Example 1

Input: n = 5

Output: 2

Explanation: The binary representation of 5 is 101, which contains two set bits.

Example 2

Input: n = 15

Output: 4

Explanation: The binary representation of 15 is 1111. All four binary digits are set bits.

Brute Force Approach

A number’s binary form contains 0s and 1s. Counting its set bits means checking these digits one at a time and counting how many are 1.

The rightmost bit can be checked using bitwise AND with 1, written as n & 1. Since 1 has only its rightmost bit set, this operation clears every other bit and keeps only the rightmost bit of n. The result is 1 if that bit is set, and 0 otherwise.

After checking that bit, shifting the number right by one position (n >> 1) removes it and brings the next bit to the rightmost position. Repeating this process checks every bit. Each result of 1 adds one to the count.

When the number becomes 0, no set bits remain to check. The final count is the answer.

Algorithm

  1. Start with a count of 0. This count will keep track of how many set bits, or bits with a value of 1, have been found.

  2. Examine the rightmost bit of the number. Using number & 1 tells us whether this bit is 1 or 0, without checking the other bits.

  3. If the rightmost bit is 1, increase the count by one. If it is 0, leave the count unchanged because zero bits do not contribute to the answer.

  4. Move to the next bit by shifting the number one position to the right. This removes the bit that was just checked and brings the next bit into the rightmost position.

  5. Repeat this process of checking, counting, and shifting until the number becomes 0. At that point, no set bits remain to be checked.

  6. Return the count. If the original number was 0, no checking is needed, and the answer remains 0.

Dry Run

Count set bits in an integer - Brute

Count set bits in an integer - Brute

Solution

#include <iostream>
using namespace std;
class Solution {
public:
// Returns the number of set bits in a non-negative integer.
int countSetBits(int n) {
// Stores the number of set bits found so far.
int count = 0;
// Examine one binary digit in each iteration.
while (n > 0) {
// AND with 1 isolates the rightmost bit.
// Add 1 if that bit is set; otherwise, add 0.
count += (n & 1);
// Discard the checked bit and move to the next position.
n >>= 1;
}
return count;
}
};
// Driver code
int main() {
int n = 15;
// Create an instance of class Solution.
Solution sol;
cout << sol.countSetBits(n) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(log N) for positive N, because the algorithm examines every binary digit once. A positive integer has ⌊log₂ N⌋ + 1 binary digits. For N = 0, the loop is skipped, and the method takes O(1) time.

Space Complexity: O(1) auxiliary space because only the counter and the current number are stored.

Optimal Approach

The idea is to count the set bits by removing one 1 at a time from the number’s binary form. Each removal represents one set bit. Once all the ones are removed, the number becomes zero, and the total number of removals gives the answer.

To remove a set bit, use n & (n - 1). Here, & performs bitwise AND: it keeps a 1 at a position only when both numbers have a 1 at that position.

Subtracting one from the current n changes the rightmost 1 into 0 and turns any zeros after it into ones. The bits before that position stay unchanged. When the original number and this smaller number are combined using AND, the rightmost 1 is cleared. The newly formed ones after it meet zeros in the original number, so they also become zero. Every other set bit remains unchanged.

Use the resulting number for the next removal and count one set bit each time. Continue until the number becomes zero. This processes exactly one set bit per step, so the final count is the number of set bits in the original number.

Algorithm

  1. Start with a count of 0. Here, the count will record how many set bits have been removed from the number.

  2. Check whether the number is 0. If it is, there are no set bits left, so the process can stop.

  3. Remove the rightmost set bit, which is the first 1 encountered when looking from right to left. Use number & (number - 1) to do this in one operation. Subtracting one changes that 1 to 0 and changes the zeros to its right into ones. Taking the bitwise AND with the original number clears that set bit while keeping all other bits unchanged. For example, 1100 becomes 1000.

  4. Increase the count by one, because exactly one set bit has been removed.

  5. Repeat the same operation on the updated number. Each repetition removes another set bit, so there is no need to examine zero bits individually.

  6. Once the number becomes 0, return the count. Since every repetition removed exactly one 1, the count is the total number of set bits in the original number.

Dry Run

Count set bits in an integer - optimal

Count set bits in an integer - optimal

Solution

#include <iostream>
using namespace std;
class Solution {
public:
// Returns the number of set bits in a non-negative integer.
int countSetBits(int n) {
// Tracks how many set bits have been removed.
int count = 0;
// Continue until no set bits remain.
while (n > 0) {
// AND with n - 1 clears the rightmost set bit
// while leaving every other set bit unchanged.
n = n & (n - 1);
// Exactly one set bit was removed in this iteration.
++count;
}
// The number of removals equals the original set-bit count.
return count;
}
};
// Driver code
int main() {
int n = 15;
// Create an instance of class Solution.
Solution sol;
cout << sol.countSetBits(n) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(K), where K is the number of set bits in the original number. Each iteration removes exactly one set bit. In the worst case, all binary digits are 1, giving O(log N) time. For N = 0, the method takes O(1) time.

Space Complexity: O(1) auxiliary space because only the counter and the current number are stored.

Interview follow-up Questions

Yes. A positive power of two contains exactly one set bit. Clearing that bit using n & (n - 1) makes the number 0. Therefore, the condition is n > 0 && (n & (n - 1)) == 0. The check n > 0 excludes zero, which satisfies the bitwise expression but is not a power of two.

Bit ManipulationTCS NQT

Read Similar Blogs

Comments0