Comparing Integers

Problem

Find out if two integers are equal without using comparison operators.

Solution

When a problem needs to be solved without basic programming devices like operators, often enough the solution will require the use of bitwise and bit shift operations.

Let’s go through the steps of an algorithm that will solve this problem. Normally, my first step would be to utilize pseudocode to create a solution, and then after that I would write out my code. In most situations, pseudocode helps to reduce complexity while solving problems. However, in this case we will be solving with bitwise operators, so working directly with code right away makes the most sense.

We will be creating a method that takes two integers and returns a boolean value as follows:

Let’s say that we have x = 3 and y = 5 as follows:

Note that I have separated the bits into groups of four for readability. I have also omitted the twenty-four 0’s on the left-hand side of each integer.

The first tricky part

In order to find out if the two numbers are equal we can use a neat little trick. The following line is the trickiest part of the solution. Everything after this is quite straightforward and simple.

If the two numbers are equal, then z will equal 0 after this operation.

If the two numbers are unequal, then z will equal a negative number after this operation. It doesn’t matter what the negative number is. It only matters that we know the number is negative.

Let’s go through it step-by-step for this example.

Note that there are twenty-four 1’s to the left of z since it is a signed 32-bit integer.

The only thing we are concerned about is the MSB (Most Significant Bit). This is the bit on the far left that signifies whether or not the number is negative. We can use this information to solve the rest of the problem.

The next step involves fully shifting our bits to the right.

Now let’s flip our bits so that our value is more intuitive.

Therefore, if z equals -1 then we want to return true since the numbers are equal, and if z equals 0 we want to return false since the numbers are unequal.

The second tricky part

Here is the second tricky part of the solution. How do we return a boolean value of true or false when we are not allowed to use comparison operators?

If we were allowed to use comparison operators then it would be quite simple. If z is all 1’s in binary then it will equal -1 which means the numbers are equal so we could just use the following line of code:

However, we are not allowed to use comparison operators, so we have to come up with another way to do this. The simplest way I can come up with is to use a HashMap as follows:

We set up two key/value pairs in our HashMap so that we can use those keys in order to return our answer in boolean.

Special Cases and Error Conditions

The method will work on the entire range of integers. Integer overflows, although they will occur in certain situations, will not affect the correctness of the algorithm.

For example, let’s pretend we have the following input:

There will be an integer overflow while executing the method, both for (x – y) as well as for (y – x).

Let’s look at this with bytes instead of integers in order to more easily visualize the overflow.

(x – y) = 127 – (-128) = 127 + 128 = 0111 1111 + 1000 0000 = 1111 1111 = -1

(y – x) = -128 – 127 = 1000 0000 – 0111 1111 = 1000 0000 + 1000 0001 = 0000 0001 = 1

Java ignores overflows completely. In binary, when we add 1000 0000 + 1000 0001, the far left 1 will drop off without Java showing any concern whatsoever.

So we are left with -1 and 1 even though we had overflows. This leaves us with a negative number as one of our results, which means that our algorithm will still function properly.

Solution in Java

GitHub – The source code for the final solution is available at GitHub.  Instructions for how to run the project locally are shown in the README.md document.

Here is the Main class that will implement the solution.

 

Unit Testing

The following MainTest class will run unit tests to verify the functionality of the Main class.