Count set bits in an integer || Bit Manipulation important logic || Intense Coding

1. Simple Method Loop through all bits in an integer, check if a bit is set and if it is, then increment the set bit count.
Time Complexity: Θ(logn) (Theta of logn)

Auxiliary Space: O(1)

2. Recursive Approach:
Time Complexity: O(log n)

Auxiliary Space: O(1)

3. Brian Kernighan’s Algorithm:
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit.
for example :
10 in binary is 00001010
9 in binary is 00001001
8 in binary is 00001000
7 in binary is 00000111
So if we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the number of times the loop executes, we get the set bit count.
The beauty of this solution is the number of times it loops is equal to the number of set bits in a given integer.
1 Initialize count: = 0
2 If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
3 Else return count
Example of Brian Kernighan’s Algorithm:

n = 9 (1001)
count = 0

Since 9 greater than 0, subtract by 1 and do bitwise & with (9-1)
n = 9&8 (1001 & 1000)
n = 8
count = 1

Since 8 greater than 0, subtract by 1 and do bitwise & with (8-1)
n = 8&7 (1000 & 0111)
n = 0
count = 2

Since n = 0, return count which is 2 now.
Time Complexity: O(logn)