Hamming Distance — Programming Interview Problem (I.)

(this article was originally written for my blog vojtastavik.com)

This is the first post of a small series focused on common technical interview challenges. You can find a lot of articles and StackOverflow answers on the similar topic. However, I would like to focus on a Swift-first approach and detailed explanation. Fore the sake of curiosity, I will also show an Objective-C version of the final algorithm. I’m going to use problems from the awesome website LeetCode. So let’s start!

(Image source: Wikipedia)

The problem: Given two integers x and y, calculate the Hamming distance. The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Every integer can be represented in a binary form as a sequence of 0 and 1. To find out more about how the binary representation of a given number works, go to this Wikipedia page.

Let’s say we have two integers, 2 and 6. Their binary representations look like this:

We need to compare the numbers and count, how many times are the bits on the corresponding positions different:

You can see that there’s only one bit which is different. The hamming distance of numbers 2 and 6 is therefore 1.

Solution

Let’s try to convert what we did above to a program. We have a function calculateHammingDistance and we need to write its implementation.

We can split the problem into two sub-problems:

Step 1: Find different bits

The most obvious solution for this would be to iterate through bits of both numbers and compare them bit by bit. Fortunately, we don’t have to do that. There’s an operator in Swift which does exactly that!

Ladies and gentlemen, let me introduce you Bitwise XOR or ^ if you will:

(Image source: Apple.com)

Thanks to this operator, finding different bits of two numbers is just one line of code:

Step 2: Count the number of different bits

Let’s take a look on how the differentBits variable looks like with our example numbers 2 and 6:

Before we proceed, we need to know about a few other interesting operators for bit manipulations in Swift:

(Image source: Apple.com)

Important: The right shifting behavior is different for negative numbers. If the number is greater than zero, the most left bit will be filled with 0 after the shift. For negative numbers, the most left bit will be filled with 1.

(Image source: Apple.com)

(Image source: Apple.com)

Our strategy for counting the number of 1 in differentBits will be to shift its bits step by step to the right, and check if the last bit is 1. If we find 1, we increment a counter, otherwise we continue until there is no 1 in differentBits. In the other words, until differentBits == 0.

Objective-C version

Summary

There are no specific edge cases we need to test our algorithm for. We don’t need to know if the integer is negative, IntMax or zero. We’re working with the integers on the bit level, and we don’t really care about the numbers they represent. There’s no possibility of overflow, because we’re only comparing already existing integers.

Trick question: What is the maximal value of hamming distance for two 32bit integers?