In this article, I’ll explain how to solve the Bit Counting algorithm challenge on Codewars.
Problem statement: Given a 32-bit signed integer, how many set bits are there?
Ex: The number 15 has four bits set.
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
Code language: plaintext (plaintext)
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
Code language: plaintext (plaintext)
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
Code language: plaintext (plaintext)
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:
00000000 00000000 00000000 00000001 (first bitmask)
00000000 00000000 00000000 00000010 (second bitmask)
...
10000000 00000000 00000000 00000000 (final bitmask)
Code language: plaintext (plaintext)
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
Code language: plaintext (plaintext)
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
Code language: plaintext (plaintext)
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).
Input | Expected value |
0 | 0 |
1 | 1 |
15 | 4 |
Max int32 2,147,483,647 | 31 |
Min int32 -2,147,483,648 | 1 |
Code
public int CountSetBits(int n)
{
int count = 0;
int mask = 1;
for (int i = 0; i < 32; i++)
{
if ((mask & n) == mask)
count++;
mask = mask << 1;
}
return count;
}
Code language: C# (cs)