Brian Kernighan Algorithm

prescript: If u are a visual learner I have created a youtube video on the same. pls, check that out. https://youtu.be/e0sVe4-JJJI

What it does : Count 1s in a binary number

Basics :

If u understand below mentioned points then there is nothing left to learn in this algorithm

1. 0s are called ‘unset bits’ in a binary number and 1s are called ‘set bits’
2. In programming languages identifier for a binary number is ‘0b’ as a prefix. for example : 0b00001010 represents 10
3. The most important point on which this algo is based
   Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost bit.
   :for example :
   10 in binary is 00001010
   9 in binary is 00001001
   8 in binary is 00001000
   7 in binary is 00000111
   U can easily comprehend from the above binaries
4. All the programming languages have bitwise operator “&” which works as u would expect it to be
   for example : 0b00001010 & 0b00001001 return 0b00001000
5. Combining point 3 and 4 if u run bitwise & operator on decimal number ’n’ and ‘n-1’ it removes the rightmost ‘set bit’ from n

Implementation:

# Function to get no of set bits in binary 

def countSetBits(n):
  count = 0
  while (n): 
    n = n & (n-1) 
    count= count + 1
  return count
# Program to test function countSetBits 
i = 9
print(countSetBits(i))

Advantage:
A normal solution that loops over the binary and increases a counter every time it finds a set bit have a time complexity of O(n)

The beauty of this solution is the number of times it loops is equal to the number of set bits in a given integer

You can find me here: https://sanchitbansal.com/