Count set bits in an integer

Posted on Updated on

Problem Statement:

Write a program to count number of 1’s in binary representation of an integer.

We suggest you think about a solution before reading further…

Solution:

  • Brute-Force solution: Loop through all the bits in an integer, AND the bit with 1 to check if its 1. Increment the count by 1 if the bit is 1. The loop iterates n-times where n is number of bits in an integer.
    • Time Complextity: O(n)
  • Brian Kernighan’s Algorithm: 
    • Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit (including the righmost set bit).
    • If we subtract a number by 1 and do AND & with itself (n & (n-1)) we unset the rightmost set bit. So doing  n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
    • This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass once per bit.
    • An integer n has log(n) bits, hence the worst case is O(log(n)). So Time Complexity is O(log(n))

Output:

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.