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?

if you need it as fast as possible, I would use a lookuptable that gets populated at compile time. Btw, as you are only interested in the hamming distance to 0, you are basically counting the bits that are set to 1, which is a bit easier than calculating the hamming distance in the general case. — 463035818_is_not_an_ai, Mar 14 '16 at 18:10
I like the way you think. You can also do something like `Integer.toBinaryString(num).length()` if you don't want to use the `for` loop. — user2004685, Mar 14 '16 at 18:12
Possible duplicate: [Count number of 1's in binary format of decimal number](http://stackoverflow.com/questions/14682641/count-number-of-1s-in-binary-format-of-decimal-number) — NathanOliver, Mar 14 '16 at 18:12
See [this](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer) and [this](http://stackoverflow.com/questions/35975574/binary-representation) — Weak to Enuma Elish, Mar 14 '16 at 18:13

stark · Answer 1 · 2016-03-14T18:37:19.700

To create a lookup table for 9 bits (since this is for Sudoku):

int dist[512];
dist[0] = 0;
for (i=1; i<512; i++)
    dist[i] = (i&1) + dist[i/2];

To avoid the initial calculation this could also be written as a memoizing recursive function.

int dist(int bits) {
    static _dist[512] = {};
    if (bits == 0)
        return 0;
    else if (_dist[bits] == 0)
        _dist[bits] = (bits & 1) + dist(bits/2);
    return _dist[bits];

gustf · Accepted Answer · 2016-03-14T18:38:21.840

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;
}

score 0 · Answer 3 · answered Mar 14 '16 at 18:24

Not sure, if this helps, but out of curiosity I implemented it via templates:

template <int N>
struct Hamming {
    enum { value = Hamming< (N/2) >::value + (N&1)};    
};
template <>
struct Hamming<0>
{
    enum { value = 0 };
};


int main() {
    std::cout << Hamming<7>::value << std::endl;
    return 0;
}

It can only be used if N is known at compile time, thus I think you will have to use something else in your case. However, it nicely demonstrates how any computation at runtime can (in principle) be completely avoided.

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

3 Answers3