Count Number Of Set Bits In An Integer

Question: Given an integer K, return count of set bits of an integer.
Input: 7
Output: 3
What is Set Bit & Unset Bit?
Before answering this question, let me ask you what exactly binary number is?
The sequence of digits with base 2 containing ONLY 1 and 0 is a binary number.
For instance, 110 base 2 is a binary number whose decimal value is 6
My aim is not to teach number system through this article, I just wanted a quick glimpse on binary number.
If you're still not sure about binary numbers I'll suggest you to first get a hold on it before reading further.
You can go here.
Binary Number System - Definition, Conversion, Examples - GeeksforGeeks
Now, coming to the question of set and unset
In layman's term, set means 1 and unset means 0
for example, given a binary number (1 1 0 1 1 0)
1 --> set (Why? because set means 1)
1 --> set
0 --> unset (Why? because unset means 0)
1 -->set
1 -->set

0 --> unset
Hence, for above binary number we have 4 set bits and 2 unset bits.
Awesome! Now we finally know what a set bit and unset bit is.
Let's now get back to the original million dollar question..
Question: Given an integer K, return count of set bits of an integer.
for instance,
if the integer is 7, then we know binary representation of 7 is (111), since 111 has 3 ones so count of set bit in it is 3.
So the output should be 3.
If the integer is 9, then we know binary representation of 9 is (1001), since 1001 has 2 ones, so count of set bit in it is 2.

Since we now understood the question, let's see some approaches to solve the question.

Approach 1:
we know integer is 32 bit (4 byte), hence we can iterate to all the bits and check which bit is set or not.
for ex:
K = 6
Binary of 6: 0000000.......00110, [Note ... represents zeroes in between]
BUT HOW TO CHECK IF A GIVEN BIT IS SET OR UNSET?
To check whether a bit is set or not we can do a bitwise AND operation.
Let's See How
Let's say my binary number is 10011, I want to check if 4th index bit is set or not.
binary : 1 0 0 1 0
index : 4 3 2 1 0
[Observe here, in binary we take index from right to left unlike array]
Algorithm To Check 4th bit is Set Or Not
1. Make right shift 4 on binary number
2. Do bitwise AND with 1
3. If the result got from executing step 1 and step 2 is 1, then it means the bit is set or else the bit is unset.

Executing Step 1 on Binary Number (1 0 0 1 0)
binary : 1 0 0 1 0
1st right shift: 0 1 0 0 1
2nd right shift: 0 0 1 0 0
3rd right shift: 0 0 0 1 0
4th right shift: 0 0 0 0 1
-----------------------------------------------------
Step 1 Result: 0 0 0 0 1
------------------------------------------------------
Executing Step 2,
Making Bitwise AND with 1, With Step1 Result which means,
Step1 Result: 0 0 0 0 1 (Step 1 result)
& 0 0 0 0 1 (And with decimal value 1)

equals ===> 0 0 0 0 1 (Decimal value of 1).
Executing Step 3,
Checking the value of step 2,
if it is 1 means the bit is set or if it is zero, bit is unset.
Here, we get 1, so the 4th bit of the given binary number is SET.
note: if we would have get 0, then in that case we can say the 4th index bit is unset.
Now, dear friends, let us generalize the algorithm, for checking if the i th bit is set or not. (here i is any random index)
Algorithm To Check if i th bit is Set Or Not
1. Make right shift i times on the number
2. Do bitwise AND with 1
3. If the result got from executing step 1 and step 2 is 1, then it means the bit is set or else the bit is unset.
Now, since we finally knows how to check if any i th index bit is set or not, we can check how many bits in the number is set. How?
--> Just iterate every bit and see whether it is set or not.
Here is a code snippet for it.

bool isIthBitSet(int number, int i)
{
    return ((number>>i) & 1) == 1;
}

int getCountOfSetBits(int number)
{
    int countOfSetBits = 0;
    for(int i=31; i>=0; i--)
    {
      if(isIthBitSet(number, i) == true) countOfSetBits++;
    }
    return countOfSetBits;
}

Let's see the time complexity. As we can see we are iterating to every bits, the time complexity is O(number of bits).
Now the question is can we optimize it further?
Yes, we can.
Now comes our beloved Brian Kernighan Algorithm. Before going deep into it, let me show you something.
I am writing some binary representations of decimal numbers below, try to find any observation.

if we see carefully,
let's say we take 11 -> 1011 and 10 -> 1010,
After the rightmost set bit of 11 all the bits after it including the rightmost set bit itself is flipped in 10 and rest of the left bits remained the same.

For instance,
11 -> 1011
The Rightmost Set bit in it is the highlighted part, 1011. Here only one bit is after & including the rightmost set bit that is itself. Let's flip it,
Then it becomes 1010 . But 1010 is 10.

Let's take one more example.
8 -> 1000 and 7 -> 0111,
The rightmost set bit of 8 is the highlighted part, 1000. Let's flip all the bits including and after rightmost set bit, which will now become 0111.
But wait, 0111 is 7 right?

Let's take one last example,
4 -> 0100 and 3-> 0011.
The Rightmost set bit in 4 is 0100. Let's flip all the bits including and after rightmost set bit, which will now become 0011.
But we know 0011 is 3.

Hence, the above observations are telling us that if we subtract one from a decimal number, it inverts all the bits after the rightmost set bit i.e. it changes 1 to 0 and 0 to 1.

In the above table, we can clearly see that if we subtract one from a decimal number, it inverts all the bits including and after the rightmost set bit i.e. it changes 1 to 0 and 0 to 1.
Now the question comes can we use the above observation to solve our problem?
Yes, we can. Let's see how.
Suppose I want to find the count of set bits in 7. We know 7 is (111) base 2 in binary and set bit count is 3 (clearly visible as three ones).
Can I say that if I do bitwise AND of 7 with 6 it will make the bits including and after the rightmost set bit in 7 to unset i.e 0.
But why?
Because all the bits including and after the rightmost set bit in 7 is already inverted in 6. (From the observation as 6 is 1 less than 7)
0 1 1 1
& 0 1 1 0
----------
0 1 1 0 i.e (6)
Let's do the same thing with the result of 7 & 6 i.e 6. I mean, let's do bitwise AND 6 with 5. it should make the bits including and after the rightmost set bit in 6 to 0.
But why?
Same reason, because all the bits including and after the rightmost set bit of 6 is already inverted in 5. (From the observation as 5 is 1 less than 6)
0 1 1 0
& 0 1 0 1
------------
0 1 0 0 i.e (4)
Let's do the same thing with the result of 6 & 5 i.e 4. I mean, let's do bitwise AND 4 with 3.
0 1 0 0
& 0 0 1 1
-----------
0 0 0 0 i.e (0)
Since, we got 0 we'll stop and we know 0 has no bit set.
We saw that bitwise AND of two consecutive numbers X and (X-1), actually turns rightmost set bit in X to 0. (Reason? Because, after and including the rightmost set bit in X all the bits are inverted in X-1)
Hence, we repeat the process and eventually stop till we turn the number to 0
So, the number of times we do BITWISE AND to unset the rightmost set bit is the count of set bits in the number.
For instance,
To calculate the number of set bits in 7,
we did,
7 & (7-1) ==> 6
6 & (6-1) ==> 4

4 & (4-1) ==> 0 (STOP!)
Here, we did 3 times bitwise AND so the count of set bits in the number seven is 3.
Let's write the algorithm,
STEP 1: IF N is equal to 0 return 0
STEP 2: Take Count = 0
STEP 3: SET N = N & (N-1), Count++;
STEP 4: IF N is equal to 0 then stop and return Count
Else go back to step 2.
Surprisingly, code for this algorithm is very short and simple.

---

int getCountOfSetBits(int number)
{
    if(number == 0) return 0;
    int countOfSetBits = 0;
    while(number != 0)
    {
        number = number & (number - 1);
        countOfSetBits++; //Counting no. of time we do AND
    }
    return countOfSetBits;
}

Coming to the Time Complexity of the code, we can see clearly the loop will execute only the number of times set bit is there in the number i.e O(K), where K is number of set bits present in the number.

But how it is better than Approach 1?
Because in Approach1 we were iterating 32 bits all the times irrespective of whether I have just 1 bit set in the number. But in second approach we would just iterate 1 time.

Thanks for reading this.
Happy Coding!