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.
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.
Output for input value of 127 and 1.
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.
Explanation:
Least significant it of an integer can be either 0 or 1. If
1. Least significant bit of integer n is 1 then n1 has 0 in LSB position and if we do bitwise AND between n and n1 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 n1 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 n1.
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.
Integer.bitCount() implementation from JDK 6.
public static int bitCount(int i) {

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;

Java2html 
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){

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 n1 has 0 in LSB position and if we do bitwise AND between n and n1 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 n1 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 n1.
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.
No comments:
Post a Comment