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```