Find the max of two numbers without using any of the comparison operators like if-else.

Here the challenge is to find the maximum of two numbers, but you can not actually compare the two numbers using something like an if statement. So, how can we go about solving this logically? Well, one of the best techniques of solving difficult questions which seem to have no answer is to rephrase the question itself, or as Einstein once said: “If I had an hour to solve a problem and my life depended on the solution, I would spend the first 55 minutes determining the proper question to ask, for once I know the proper question, I could solve the problem in less than five minutes.”

Rephrasing the question so that we don’t use conditional (if) statements

With that in mind, let’s break down the question to see if we can get it into a form that does not use a conditional statement like “if”. Since we can’t use our normal comparison operators, it’s good to think in terms of other operators that can provide similar functionality. Binary is a good option – because binary operators generally allow you to solve conventional problems differently. So, let’s keep binary on our minds as we try to solve this problem.

First off, let’s call the two numbers from which we want to find the maximum, x and y – and we can assume that x and y are the numbers passed into the function that will return the max. We can then say that if x is greater than y, then we will return x, because x is greater. Otherwise we return y, because y is greater.

The process of rewording the problem to not use a comparison operator

– Let’s try to rephrase our last statement – if y is greater than x then we also know that x – y is a negative number. In which case, we would return y. Otherwise, if x – y is not a negative number (which means x – y is a positive number or 0), we return x because that is clearly the greater number. To summarize, if x – y is negative, return y. Otherwise we return x.

– Now, let’s try to rephrase our most recent statement. Let’s say we have some other variable – call it “i”. If x – y is negative, then let i be equal to 1, and if x-y is a positive number, we let i be equal to 0. We could just say that we want to return x – i * (x – y).

– This means that if y is greater than x, then “i” would be 1 and we would return x – 1 * (x – y), which is x -x + y, which is just “y”. And if x is greater than y, then “i” would be 0, and we would return x – 0 * (x – y), which is just 0.

– Let’s summarize that last statement and highlight it since it’s important:

If (x - y) is negative, then set i = 1; otherwise 
set i = 0.  Then return x - i * (x - y) .

Now it looks like we are making some progress towards not having to use a conditional statement, and rephrasing the question (actually more like breaking it down) to make it easier for us to solve – just like Einstein said.

But, before we proceed further with our solution, we have to talk about two’s complement notation – which is something that you should be familiar with before you see the final solution.

Using binary two’s complement notation to help find a solution

If we convert a negative number to binary, then we know that the most significant bit will always be a 1 – because that is how negative numbers are differentiated from positive, non-negative numbers in two’s complement notation. Two’s complement notation is basically a way to represent both positive and negative numbers in binary, and also simplifies arithmetic operations done in binary.

Almost all modern processors use two’s complement notation to store numbers. And, we also know that the most significant bit of a binary positive number stored in two’s complement notation will always be a 0. As a quick example, if 8 bits are being used, then the number 5 will be represented by 00000101 in two’s complement notation. If we want to convert the number to -5 in two’s complement notation, then we simply flip the bits (so that 1 becomes 0 and 0 becomes 1), and then we add 1 to the result. So, flipping the bits will give us 11111010, and adding 1 to that will give us 11111011. So, you can see from our example that the negative number has a 1 in the most significant bit position – which is the leftmost bit, and the positive number has a 0 in that same position.

Remember our last statement before we started talking about two’s complement notation? Well, it was this: If (x – y) is negative, then set i = 1; otherwise set i = 0. Then return x – i * (x – y) .
This means that we can just set the variable “i” to equal the most significant bit of (x – y) in binary. Remember, this is because i will be 1 when x – y is negative and i will be 0 when (x-y) is a non-negative number. So, if we set z to equal (x – y), then we can say that we want to set i to equal the most significant bit of z in binary, and we then want to return x – i * z. Think that through carefully and make sure you understand that, because it really is the heart of the solution to this problem.

Now, we seem to have a solution that does not use any conditionals. Let’s write some code that actually implements the algorithm described above.

int findMax( int x, int y)
{
   int z = x - y;
   int i  = (z  >>  31)  &  0x1;
   int  max  =  x - i  *  z;
   return max;
}

Explanation of solution to finding the max without comparison operators

In the code above, we assume that because z is an integer it will be 32 bits – which is a safe assumption. From our algorithm above, we need to know if z is either a positive number or a negative number, because that will tell us which number is larger. And that is why we shift z by 31 bits to the right – because we just want to have what the most significant bit of z in the lowest position – remember that we are just interested in the most significant bit of z . Then, we AND that bit with the binary representation of 1 (which will basically be 31 zero’s that end with a 1) so that we get it back into an integer format (as opposed to binary), and we store that value for i. The other lines of code follow our algorithm explained in extensive detail above, and they should be self explanatory.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

3 thoughts on “Find Max Without Comparison”

WordPress › Error

There has been a critical error on your website.

Learn more about debugging in WordPress.