optimal Hamming Distance implementation
Anyone know how to optimally implement a Hamming distance and weight function?
My first stab is this code:
/**
* Calculates the <b>Hamming distance</b> between 2 ints.
* The ints are viewed as binary strings, so the result is the number of bits where the 2 ints differ.
* In particular, this method simply returns <code>{@link #hammingWeight hammingWeight}( i1 ^ i2 )</code>.
*
* @see <a href="http://en.wikipedia.org/wiki/Hamming_distance">Wikipedia article on Hamming Distance</a>
*/
publicstaticint hammingDistance(int bits1,int bits2){
return hammingWeight( bits1 ^ bits2 );
}
/**
* Calculates the <b>Hamming weight</b> of an int.
* The int is viewed as a binary string, so the result is the number of bits equal to 1.
*
* @see <a href="http://en.wikipedia.org/wiki/Hamming_distance">Wikipedia article on Hamming Distance</a>
*/
publicstaticint hammingWeight(int bits){
int weight = 0;
for (int i = 0; i < 32; i++){
int lsb = bits & 1;// bitwise AND with 1 leaves just the least significant bit of i
weight += lsb;// add lsb to the result
bits >>>= 1;// unsigned right shift i by 1 bit so that the next iteration detects the next bit; could use signed shift too (any performance difference?)
}
return weight;
}
I think that that code is corrrect, and below is my test code:
privatestaticvoid test_hamming()throws Exception{
System.out.println();
System.out.println("test_hamming:");
if (hammingWeight(Integer.MIN_VALUE) != 1)thrownew Exception("hammingWeight(Integer.MIN_VALUE) = " + hammingWeight(Integer.MIN_VALUE) +" != 1");
if (hammingWeight(Integer.MAX_VALUE) != 31)thrownew Exception("hammingWeight(Integer.MAX_VALUE) = " + hammingWeight(Integer.MAX_VALUE) +" != 31");
if (hammingWeight(0) != 0)thrownew Exception("hammingWeight(0) = " + hammingWeight(0) +" != 0");
if (hammingWeight(1) != 1)thrownew Exception("hammingWeight(1) = " + hammingWeight(1) +" != 1");
// could likewise do all the other powers of 2...
if (hammingWeight(15) != 4)thrownew Exception("hammingWeight(15) = " + hammingWeight(15) +" != 4");
if (hammingDistance(Integer.MIN_VALUE, Integer.MAX_VALUE) != 32)thrownew Exception("hammingDistance(Integer.MIN_VALUE, Integer.MAX_VALUE) = " + hammingDistance(Integer.MIN_VALUE, Integer.MAX_VALUE) +" != 32");
if (hammingDistance(0, 1) != 1)thrownew Exception("hammingDistance(0, 1) = " + hammingDistance(0, 1) +" != 1");
if (hammingDistance(15, 16) != 5)thrownew Exception("hammingDistance(15, 16) = " + hammingDistance(15, 16) +" != 5");
System.out.println("All tests passed");
}
My question concerns the algorithm inside the above hammingWeight method: is there any way to count the number of bits set to 1 besides doing a sequential examination like that method currently does?
Any clever bit twiddling logic that I am ignorant of?
[5406 byte] By [
bbatmana] at [2007-10-2 13:38:08]
I too am not sure if the code you typed in is correct, but it inspired me to google "0x55555555" and that turned me on to tons of sources that discuss this topic, which apparently is most commonly known as "bit counting" (and not Hamming weight, which was what my original search was on).
Your code is one possibility for a fast approach.
Another is a table lookup, with the usual choice being a 256 element table that lists the bit counts of all possible bytes. For an int, you get each of its 4 bytes by shifting and use them as indices directly into this table (and for java, you will need to take make sure that the byte is unsigned by doing & 0xFF with it).
And if your machine does really fast int multiplies (e.g. apparently some of AMD's latest cpus are like this), there is possibly an even faster algorithm that uses a single multiply.
The best single source for this type of computation that I found is
http://graphics.stanford.edu/~seander/bithacks.html
with
http://aggregate.org/MAGIC/
http://www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=386
http://www.sjbaker.org/steve/software/cute_code.html
http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.cit.gu.edu.au/~anthony/info/C/bit_programming.txt
also being good, and with
http://mandala.co.uk/java/bitutils/BitUtils.java
offering code examples in java.
Yeah, table lookup is such an obvious thing to do that I should have thought of that myself--kinda embarassed that I didn't.
I don't have the time to do it now myself, but I am curious to see how the table lookup benchmarks against the best of the bit twiddling algorithms. My understanding is that cpu and caching are so critical that only benchmarking can determine what is best for a particular machine.
I also wonder if the latest JVMs are intelligent enough on x86 architectures to use the XLAT instruction that you mentioned for small tables like what this case would use.
Sorry that you seem to have got your feelings hurt from my last post--no offense was meant, you turned me on to some good stuff.
I thought that my original posting was clear that I wanted optimal performance.
Do you have any good references proving that Java is so bad on performance for applications like this?
The only related study that I can think of is the extensive numerical/scientific benchmarking done here:
http://www.shudo.net/jit/perf/
That guy found that Java compares quite decently with C/C++.
To followup: I just discovered, while looking for something else, that Sun added several bit logic methods to the Integer and Long classes for Java 1.5.
I would never have posted this in the first place had I known that those methods existed...
marlin314: it looks like they used essentially the same code as you originally posted; from the Integer class:
/**
* Returns the number of one-bits in the two's complement binary
* representation of the specified <tt>int</tt> value. This function is
* sometimes referred to as the <i>population count</i>.
*
* @return the number of one-bits in the two's complement binary
*representation of the specified <tt>int</tt> value.
* @since 1.5
*/
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;
}
