# 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))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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:

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