How to find the number of set bits in an integer

Overview

The number of set bits in an integer is the number of 1s in the binary representation of the integer.

For example:

Integer Binary Representation Number of set bits
4 0100 1
7 0111 3
15 1111 4

Brian Kernighan’s algorithm

To count the number of set bits, the algorithm turns off the rightmost set bit until the number becomes zero.

The following are the steps of the algorithm.

  1. Set the counter variable setBitCounter to zero.
  2. Run a loop while the number is greater than zero.
    • Clear the rightmost set bit of the number.
    • Increment the setBitCounter by 1.

How do we clear the rightmost set bit of a number?

The following expression can be used to clear the rightmost set bit of a number.

number = number & (number - 1);

The expression number - 1 flips all the bits after the rightmost set bit of the number.

For example:

6 - 0110
7 - 0111

7 & 6 = 0110

Code

public class Main {
    public static int countSetBits(int number) {
        if (number == 0) {
            return number;
        }
        int setBitCounter = 0;
        while (number != 0) {
            number = number & (number - 1);
            setBitCounter++;
        }
        return setBitCounter;
    }
    public static void main(String[] args) {
        System.out.println("The number of set bit counter for 7 is " + countSetBits(7));
        System.out.println("The number of set bit counter for 15 is " + countSetBits(15));
        System.out.println("The number of set bit counter for 8 is " + countSetBits(8));
    }
}

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)