Counting number of set bits in an integer.

In binary representation of an integer bit 1 is called set bit. Calculating number of set bits in an integer is an interesting question that is asked sometimes in programming interview. There is a method in JDK using which we can calculate number of set bits in an integer which is Integer.bitCount(). Its implementation is little bit complex and different from below discussed 2 methods.  
Integer.bitCount() implementation from JDK 6.

public static int bitCount(int i) {         // HD, Figure 5-2         i = i - ((i >>> 1) & 0x55555555);         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);         i = (i + (i >>> 4)) & 0x0f0f0f0f;         i = i + (i >>> 8);         i = i + (i >>> 16);         return i & 0x3f;     }

Java2html

In this post we will see how number of set bits can be calculated without using Java api Integer.bitCount() method.
In first method we use & (bitwise AND operation) and >>> operator (logical right shift operator) to calculate number of set bits.

import java.util.Scanner; /*Program to calculate number   * of set bits in an integer using   * bit shifting and masking.  * @author Anuj  *   * */ public class NumberOfBits {          static int calculateSetBits(int n){         int count = 0;         while(n!=0){             if((n & 1)==1){                 count++;             }             n>>>=1;         }         return count;     }     public static void main(String[] args) {         System.out.print("Enter number:");         Scanner sc = new Scanner(System.in);         int num = sc.nextInt();         System.out.println("Number of set bits in "+num+" are:"+calculateSetBits(num));     } }

Java2html

Output for input value of 127 and -1.

Enter number:127
Number of set bits in 127 are:7

Enter number:-1
Number of set bits in -1 are:32

Explanation:
In while loop number is applied & operator (bitwise AND) with 1 to check if least significant bit is one, if it is one than count is increased by one.  And after that bits in number is shifted one place right by using >>> (logical right shift operator). Loops keep on running until number becomes 0 due to right shift of bits.
In above program while loop runs for each bits in an integer i.e. 32 times.

There is another way to calculate number of set bits in an integer more efficiently by using Brian Kernighan’s algorithm. In this algorithm while loop runs only as many times as number of set bits in an integer. For example, 128 has only one set bit and if we calculate using above method of masking and bit shifting while loop will run 32 times but by using Brian Kernighan’s method it will run only one time.

Brian Kernighan algorithm implementation.

static int brianKernighanMethod(int num){         int count = 0;         while (num!=0) {             num = num & (num-1);             count++;         }         return count;     }

Java2html

Explanation:
Least significant it of an integer can be either 0 or 1. If-
1. Least significant bit of integer n is 1 then n-1 has 0 in LSB position and if we do bitwise AND between n and n-1 the resulting number has 0 in LSB position.
2. If LSB is 0 then all bits starting from LSB till first occuring 1 bit is toggled. For example if binary representation of n is 10100 then n-1 is 10011. In this case also the first place where 1 bit occurs starting from LSB becomes 0 in original number after bitwise AND with n-1.

The point to not that in Brian Kernighan’s method of finding number of set bits the number of times loop run is equal to number of set bits. So if number is 128 whose binary representation is 10000000 having only one set bit, then using Brian Kernighan’s method loop will run only one time.