Count set bits in an integer using Brian and Kerningham Algorithm in Python

In this article, we will learn Brian and Kerningham’s Algorithm to count the number of set bits of a number.

Count set bits in an integer using Brian and Kerningham Algorithm in Python

We know that if we subtract 1 from a decimal number then it flips all the bits starting from the right side till it encounters a set bit(i.e. 1) including the set bit.

binary representation of 8 is 00001000

binary representation of 7 is 00000111

Now, suppose we are given a number ‘num’ and if we do bitwise AND of (num) and (num-1) then we unset the rightmost set bit of num. Hence if we perform bitwise AND of num and num-1 in a loop and store the result in num itself then the number of times this loop iterates is the count of set bits of the given number num.

Code:

# Function to count number of set bits of a number 
def cntSetBits(num): 

  cnt = 0
  while (num): 
    num = num & (num-1) 
    cnt+= 1
  
  return cnt 


# Driver Program 
num = 5
val=cntSetBits(num)
print("No. of set bits are {}".format(val)) 

Output:

No. of set bits are 2

Time Complexity: O(log(num))

Recursive Implementation: 

We can also apply a recursive approach to this algorithm

# Recursive Function to count number of set bits of a number 
def cntSetBits(num): 
  if (num == 0): 
    return 0
  else:
    return 1 + cntSetBits(num & (num - 1))


# Driver Program 
num = 5
val=cntSetBits(num)
print("No. of set bits are {}".format(val)) 

Output:

No. of set bits are 2