Write a function which takes in two integers and returns the Hamming distance between them. The Hamming distance is defined as the number of positions at which the corresponding bits of each input differ. For example, the Hamming distance of \(1\) and \(4\) is \(2\), because \(0001_{2}\) and \(0100_{2}\) have 2 bits that differ. The Hamming distance of \(7\) and \(10\) is \(3\), because \(0111_{2}\) and \(1010_{2}\) have 3 bits that differ.

Continuing on the trend from the previous challenge, you must not use any bitwise operators (&, |, ^, ~, <<, >>). You may use arithmetic operators (+, -, *, /, %).

You must also not use any built-in functions to count bits, such as int.PopCount in .NET, std::popcount in C++, the POPCNT instruction in x86, or any equivalent functionality in your chosen language.

Solution

Were the “pop count” instruction and XOR (^) operator allowed, this could be achieved in one line using int.PopCount(a ^ b) - however the point of this challenge is to roll your own solution!

First, take note of the fact that while bitwise operators are forbidden, arithmetic operators are allowed. You simply need to iterate through the bits of a number, counting how many locations where the bits differ.

int HammingDistance(int a, int b)
{
    int distance = 0;
    
    while (a > 0 || b > 0)
    {
        int aBit = a & 1;
        int bBit = b & 1;
        
        if (aBit != bBit)
            distance++;
            
        a >>= 1;
        b >>= 1;
    }
    
    return distance;
}

However this solution would be invalid as it utilises the & operator and >> operator which are forbidden. So let's rewrite those sections.

First, we see on lines 7 and 8 that aBit and bBit are equal to the LSB of a and b respectively. This is actually an efficient way to verify if a number is odd or even. Since even numbers are of the form \(2n\), and odd numbers are in the form \(2n+1\), we can assume that any number which has a \(1\) in the \(2^0 = 1\) place is an odd number.

To write this another way, we can use the % (remainder) operator. If we have a remainder after dividing a number by \(2\), then that number was in fact odd.

Next, let's take a look at lines 13 and 14. We see a shift-right by 1. Since this shifts the digits of a binary number to the right, and the digits of a binary number are in the form \(2^n\), this is actually equivalent to dividing by \(2\).

That's everything! Therefore a valid solution might look like this:

int HammingDistance(int a, int b)
{
    int distance = 0;
    
    while (a > 0 || b > 0)
    {
        <mark>int aBit = a % 2;</mark>
        <mark>int bBit = b % 2;</mark>
        
        if (aBit != bBit)
            distance++;
            
        <mark>a /= 2;</mark>
        <mark>b /= 2;</mark>
    }
    
    return distance;
}