There are multiple ways to count number of 1's or set bits in a integer number in Java. You can use bitwise and bit shift operator by your own, or, you can use Java API to count number of set bits. Java 1.5 added two utility method called bitCount(int i) which returns number of 1's in your integer number, java.lang.Long class has similar bitCount(long number) for long primitives. As I have said earlier, Coding questions are important part of any Java interview, and from that recursion and bitwise operations are most popular. Questions like, How to Swap two numbers without temp variable or How to find if a number is positive or negative are some of such questions, which you see now and then in various Java interviews. In this Java tutorial, we will see, How to count number of set bits in a number, for those who don't know what is set bit, it's bit with value 1. For example 2, which is binary 0010 has just one set bit. On the other hand 10, which is 1010 in binary has two set bit or number of one's. In most of cases, Interviewer will ask you to write a Java method without using API. In this article, we will see couple of ways to calculate number of set bit in a number on Java program.
Question:
Write a function with signature int countOnes(int a), method should return number of bits that are "set" or "on" in the binary representation of number provided. For example, countOne(10) should return 2, because binary format of 10, which is 1010 has two bits on.
Counting number of set bit using Java API method
Before writing your own method to count number of 1's let's have a look at Java API. Integer.bitCount(int number) and Long.bitCount(int number) are two super easy method which can give you count of number of set bits in Java int or Java long primitive type. These methods are added from Java 1.5 and there code is based on Hacker Delight book. Here is how bitCount(int i) looks like form java.lang.Integer class :
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;
}
You can see, its based on hacker delight, figure 5-2.
Simple way to count number of 1's in a Java Integer
Integral numbers represented by int and long primitive are represented as 2's complement binary format. Also worth knowing is size of int primitive is 32 bit and size of long is 64 bit. If we go with simplest way, we can check LSB(Least Significant Bit) of number by doing AND operation with 1. This can give us count of 1's if we shift bits on right direction. We can use right shift without sign operator for that. Here is sample code to count number of 1's in Java integers :
public static int countOne(int number){
int count = 0;
for(int i =0; i<32; i++){
if( (number&1) == 1) {
count++;
}
number = number >>> 1;
}
return count;
}
Now if you write this method, Interviewer will most likely ask you about optimization. If you look closely, you can see that this method always loop 32 times, which is size of int. If you write similar method for long, it will loop 64 times, can you think what to optimize now? You can optimize this loop. Instead of making loop proportional to size of bits, you can make it proportional to number of set bits. here is a modified version :
public static int countSetBits(long number){
int count = 0;
while(number>0){
++count;
number &= number-1;
}
return count;
}
In this function, we are using AND operation and number -1 to gradually reduce number of 1's from original number. It means, this loop will only runs 4 times, if number contains 4 set bits. Here is complete Java program to count number of set bits on numbers.
/**
* Java Program to count number of 1's in a integer.
* @author Javin Paul
*/
public class CountSetBits {
public static void main(String args[]){
System.out.println("Java method to count number of 1's in a integer");
System.out.printf("Number of one's in %d is %d %n", 2, countOne(2));
System.out.printf("Number of one's in %d is %d %n", 3, countOne(3));
System.out.printf("Number of 1's in %d is %d %n", 10, countOne(10));
//A short and sweet Java API trick to find count of set bits in a integer or long
System.out.println("Counting number of set bits on integer and long using Java API");
int count = Integer.bitCount(2);
System.out.printf("Number of set bit on %d is %d %n", 2, count);
System.out.printf("Number of set bit on %d is %d %n", 3, Integer.bitCount(10));
//One optimized way to count number of one's in a number in Java
//this method is proportional to number of set bit's rather than bit size e.g. 32 for int, 64 for long
System.out.println("Another optimized Java method to count number of set bits");
System.out.printf("Number of set bit on %d is %d %n", 2, countSetBits(2));
System.out.printf("Number of set bit on %d is %d %n", 3, countSetBits(3));
}
/**
* This method is not optimized, as it iterates 32 times for integer numbers
* in all cases, can you optimize it?
*/
public static int countOne(int number){
int count = 0;
for(int i =0; i<32; i++){
if( (number&1) == 1) {
count++;
}
number = number >>> 1;
}
return count;
}
/**
* Optimized version of previous one, loop is proportional to number of 1's
* instead bit size of number.
*/
public static int countSetBits(long number){
int count = 0;
while(number>0){
++count;
number &= number-1;
}
return count;
}
}
Output:
Java method to count number of 1's in a integer
Number of one's in 2 is 1
Number of one's in 3 is 2
Number of 1's in 10 is 2
Counting number of set bits on integer and long using Java API
Number of set bit on 2 is 1
Number of set bit on 3 is 2
Another optimized Java method to count number of set bits
Number of set bit on 2 is 1
Number of set bit on 3 is 2
That's all on How to count number of set bits or 1's on integer number in Java. We have seen one way of doing it using Java bitwise and bit shift operator and further optimized that. By the way, there can be multiple ways of doing this, using bitwise operator. If you love playing with bits, you must check hackers delight, an awesome book on bit twiddling.
Tidak ada komentar:
Posting Komentar