Algorithm Explained: Counting set bits in a 32-bit signed integer

Problem statement: Given a 32-bit signed integer, how many set bits are there?

Ex: The number 15 has four bits set.

In this article I’ll explain how I’d approach this problem.

Approach

How do I know if a bit is set?

A bit can either be 0 or 1. A bit is set if its value is 1.

In order to know how many bits are set in an integer, I’ll need to look at the binary representation of the integer and count how many bits are equal to 1.

This is the 32-bit binary representation of 15:

00000000 00000000 00000000 00001111

This has four set bits. I can tell this by looking at it.

How can I tell if a bit is set programmatically?

I can use the bitwise AND (&) operator with a bitmask.

When two bits are ANDed, the result is 1 only if both bits are 1:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

The & operator ANDs each position in two numbers. The result is a number with the bits set only where it was set in both numbers.

Therefore, in order to tell if the first bit is set, I would use a bitmask with the first bit set and check if the resulting number is equal to the bitmask:

  00000000 00000000 00000000 00001111
& 00000000 00000000 00000000 00000001 (bitmask)
------
= 00000000 00000000 00000000 00000001

Because the resulting number equals the bitmask, I know the first bit is set in the other number.

How can I check all 32 bits?

To check the first bit I would use a bitmask with the first bit set. To check the second bit, I would use a bitmask with the second bit set. And so on.

In other words, I will have 32 bitmasks, like this:

Position 1  00000000 00000000 00000000 00000001
Position 2  00000000 00000000 00000000 00000010
...
Position 32 10000000 00000000 00000000 00000000

To increment the bitmask, I can use the bitwise LEFT-SHIFT (<<) operator.

This shifts the bits to the left by the specified count.

  0001
<<   1             
------
= 0010

Don’t right-shift the signed integer

Can’t I just right-shift the integer and keep ANDing with the bitmask of 1?

No.

The integer is signed, which means it can be negative. Right-shifting a negative integer does not work the same as right-shifting a positive integer. Instead of simply moving the bits one to the right, it moves the bits one to the right and then fills the bits to the left with 0’s.

For example, I’m right-shifting this negative number by 1:

  1000
>>   1             
------
= 1100

If this worked like it does with positive integers, then the result would be 0100. But it fills the left bits with 1’s, which is why the result is 1100 instead. This is why you shouldn’t right-shift a signed integer if you’re trying to count the set bits.

Test cases

Now that I have an idea of how to solve this problem I can write test cases. I like to have a mix of base cases (0 and 1), a random case (15) that I can manually verify, and edge cases (min and max int32).

InputExpected value
00
11
154
Max int32
2,147,483,647
31
Min int32
-2,147,483,648
1

Code

public int CountSetBits(int number)
{
	int count = 0;
	int mask = 1;
	for (int i = 0; i < 32; i++)
	{
		if ((mask & number) == mask)
			count++;
		mask = mask << 1;
	}
	return count;
}

Leave a Comment