Count set bits in an integer

# Count set bits in an integer

Problem Statement:

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

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: