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.

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))
public class CountSetBits {

	public static void main(String[] args) {		
		int number = 127;		
		//Brian Kernighan’s Algorithm
		System.out.println("Brian Kernighan : Number = " + number + " Set bits = "+countSetBits_BrianKernighan(number));
		//Brute Force
		System.out.println("Brute Force Sol : Number = " + number + " Set bits = "+bruteForceMethod(number));

	}

	//Brian Kernighan’s Algorithm : Loops as many no.of 1's are present in number
	private static int countSetBits_BrianKernighan(int number){
		int count = 0;		
		while(number > 0){	//loop and swap the last 1 bit in number. So loop till num > 0
			count++;
			number = number & number-1;
		}		
		return count;
	}

	//Brute Force : AND with 1 and right shift every bit, loops 32 times
	private static int bruteForceMethod(int number){
		int count = 0;
		for(int i =0; i < 32; i++){
			if((number & 1) == 1){
				count++;
			}
			number  = number >> 1;
		}
		return count;
	}

}

Output:

Brian Kernighan : Number = 127 Set bits = 7
Brute Force Sol : Number = 127 Set bits = 7

 

 

Leave a Reply

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