Count set bits in an integer
First, let's try to understand what it means to count set bits. For instance, we have the number 7. How many set bits 7 has? To answer this question, we need to write 7 in binary form and count 1.
As you can see, 7 has three 1, so it has three set bits. We're not going to talk about Hamming weight algorithm. We will try to find the simplest way.
Approach
We're going to use the bitwise AND operator to check the first bit. As you know, & return 1 only if both bits are 1.
For instance, 0101&1 = 0001 and 0110&1=0 This simple operation helps to know if the first bit is1 or 0. If it's 1 we increment the result value. We just checked the first bit and need to validate the next one. To do this, we can shift the bit representation to one bit to the right and continue counting.
Code
public int CountSetBits(int value)
{
int result = 0;
while (value != 0)
{
int firstBit = value & 1;
if(firstBit == 1)
{
result++;
}
value >>= 1; // devide by 2
}
return result;
}
Time complexity: O(Log(n)). Why log(n)? Because shifting the binary representation of a number to the right by one means dividing the number by 2
