Simple and Quick way to calculate the hamming distance of a binary integer to 0?

Question

I'm writing a Sudoku solver and I have to calculate the what I learned was called the hamming distance of an int to 0, e.g. the hamming distance of 7 (111 in binary) to 0 is 3. So I simply do:

for(int dist = 0 ; num != 0 ; num>>=1) dist += (num&1);

Although that works fine, I find it a bit clumsy. I tried to come up with a binary operation trick to calculate the distance (mostly for fun), but I could only find a way that works for a distance of 1:

(num-1) ^ ((num<<1)-1) == num → true only if hamming dist to 0 == 1

I looked on StackOverflow and on the Net, but I couldn't find anything.

Assuming that num is never negative and always smaller than 512, is there a nicer/more elegant way to evaluate it, perhaps some binary operations tricks? If not, given the assumptions above, is there an approximation of the hamming distance that would always be within an error < 1?

Answer 1

In java you can use the static method Integer.bitCount(int i)

If you need it in another language, this is the java source which should be pretty strait forward to translate.

/**
 * Returns the number of one-bits in the two's complement binary
 * representation of the specified {@code int} value.  This function is
 * sometimes referred to as the <i>population count</i>.
 *
 * @param i the value whose bits are to be counted
 * @return the number of one-bits in the two's complement binary
 *     representation of the specified {@code int} 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;
}