Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?

Question

Find the maximum of two numbers. You should not use if-else or any other comparison operator. I found this question on online bulletin board, so i thought i should ask in StackOverflow

EXAMPLE Input: 5, 10 Output: 10

I found this solution, can someone help me understand these lines of code

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}

Solution 1

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

Let's dissect this. This first line appears to be straightforward - it stores the difference of a and b. This value is negative if a < b and is nonnegative otherwise. But there's actually a bug here - if the difference of the numbers a and b is so big that it can't fit into an integer, this will lead to undefined behavior - oops! So let's assume that doesn't happen here.

In the next line, which is

int k = (c >> 31) & 0x1;

the idea is to check if the value of c is negative. In virtually all modern computers, numbers are stored in a format called two's complement in which the highest bit of the number is 0 if the number is positive and 1 if the number is negative. Moreover, most ints are 32 bits. (c >> 31) shifts the number down 31 bits, leaving the highest bit of the number in the spot for the lowest bit. The next step of taking this number and ANDing it with 1 (whose binary representation is 0 everywhere except the last bit) erases all the higher bits and just gives you the lowest bit. Since the lowest bit of c >> 31 is the highest bit of c, this reads the highest bit of c as either 0 or 1. Since the highest bit is 1 iff c is 1, this is a way of checking whether c is negative (1) or positive (0). Combining this reasoning with the above, k is 1 if a < b and is 0 otherwise.

The final step is to do this:

int max = a - k * c;

If a < b, then k == 1 and k * c = c = a - b, and so

a - k * c = a - (a - b) = a - a + b = b

Which is the correct max, since a < b. Otherwise, if a >= b, then k == 0 and

a - k * c = a - 0 = a

Which is also the correct max.

Solution 2

Here we go: (a + b) / 2 + |a - b| / 2

Solution 3

Use bitwise hacks

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

If you know that INT_MIN <= x - y <= INT_MAX, then you can use the following, which is faster because (x - y) only needs to be evaluated once.

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

Source : Bit Twiddling Hacks by Sean Eron Anderson

Solution 4

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

This is based on the same technique as mike.dld's solution, but it is less "obvious" here what I am doing. An "abs" operation looks like you are comparing the sign of something but I here am taking advantage of the fact that sqrt() will always return you the positive square root so I am squaring (a-b) writing it out in full then square-rooting it again, adding a+b and dividing by 2.

You will see it always works: eg the user's example of 10 and 5 you get sqrt(100 + 25 - 100) = 5 then add 10 and 5 gives you 20 and divide by 2 gives you 10.

If we use 9 and 11 as our numbers we would get (sqrt(121 + 81 - 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11

Solution 5

The simplest answer is below.

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}

View more solutions

Comments

[starblue]

I'd consider looking at the sign bit cheating, as it's basically the same thing the processor does for <.

[Tony Delroy]

For C++ at least, from 5.8.3, discussing E1 >> E2: "If E1 has a signed type and a negative value, the resulting value is implementation-defined.", so "c >> 31" may or may not shift a sign bit from the most- to least-significant bit....

[Antti Haapala -- Слава Україні]

and there is no telling that bit 31 is the sign bit anyway.

[Antti Haapala -- Слава Україні]

Anyway, this question should be closed because no-one reads the question text, nor the tag which is C.

[kaartic]

Just because nobody else has noted it. This is the famous bit twiddling hack found here, in a disguised form.

[Eric]

BTW, the code works only when (a-b) doesn't overflow, if it does, you need a more complex solution.

[Peter Taylor]

All of this assuming no overflows.

[templatetypedef]

@Peter Taylor- I don't think there's any problem here if there is an overflow (provided it doesn't trap to an exception). Unless I'm mistaken, all the math here still works mod 2^32. Is there something I missed?

[Senthil Kumaran]

Do you know the mathematical logic behind this?

[templatetypedef]

@mike.did: Can you do |a - b| without any conditionals?

[Peter Taylor]

@templatetypedef, suppose a = 0x80000000 (the min value of an int) and b = 1. What is c?

[Greg Hewgill]

@Senthil: Just consider both cases (a > b and b > a), substitute and simplify.

[templatetypedef]

@Peter Taylor- That's a good point. Note that I didn't come up with this answer; I was just explaining the OP's code. :-) But you are correct that this will break if the numbers are too far apart.

[Ani]

Why do we need the & 0x1? The higher bits will be already wiped by the bit-shift.

[Keith Irwin]

It's kind of a stretch to assume that absolute value is an operator which can be used for this problem. It's a good answer, mathematically, but I doubt it would be accepted.

[mike.dld]

@templatetypedef: for ints it's (a - b) & MAX_INT, ((a - b) shl 1) shr 1 and more. With floating point, there's fabs.

[Peter Taylor]

@templatetypedef, I know: I was partway through writing a very similar answer when you posted yours. I was just pointing it out for the benefit of OP.

[Peter Taylor]

@Ani, the top bit is shifted into every position it passes through. The alternative would be max = a + (c >> 31) * c

[mike.dld]

@templatetypedef: not quite correct on ints, but fabs is totally there :)

[Keith Irwin]

@Ani The >> operator propagates the left most bit for signed ints. For unsigned ints, it would be unneeded. In languages which have it, the >>> operator could be used to always fill 0s, also allowing us to remove it.

[Ani]

@Keith Irwin: Yes, it depends on whether an arithmetic or logical shift is used. The answer should clarify.

[starblue]

-1 Wrong on ints, for example (3 + 2) / 2 + |3 - 2| / 2 = 2 + 0 = 2 != 3.

[Svante]

@starblue: That would assume that division always rounds, which is a bit of a stretch (even if some popular programming languages do this). (3 + 2) / 2 + |3 - 2| / 2 = 5/2 + 1/2 = 3. Mathematically, you can get the absolute by squaring, then taking the positive root.

[Michael Foukarakis]

@starblue: ((3+2) + |3-2|)/2 = 3 Looks spot on from over here.

[starblue]

@Michael Foukarakis Yes, that's more correct, though it will also fail on overflow.

[CashCow]

I think you'll need to divide by 2 at the end because a+b and a-b may be odd, but otherwise good answer. And you can do |a-b| without conditionals cheatingly by squaring it then finding the square root.

[Matthieu M.]

note that the first proposal breaks the "no comparison operator" constraint.

[Michael Foukarakis]

@starblue: Indeed, all solutions based on add/sub will inevitably overflow. I think Prasoon Saurav's answer might be the safest way to go about this.

[Tony Delroy]

the >> operator applied to a negative left-hand argument has implementation defined behaviour, so @KeithIrwin's "propagates the left most bit" is best qualified with "in mainstream modern systems" or similar.

[Christian Gibbons]

With the difference in performance of multiplication and logic operations, instead of masking out all but the LSb after the shift, we could use the resulting all-ones/all-zeros as a bitmask. int k = c >> 31; int max = a - (k & c); Of course this relies on the compiler's implementation of right-shift to be arithmetic for signed numbers, but we're already making assumptions when shifting by the magic-number 31.

[Dvole]

a * a will easily overflow

[Alex Yu]

Look careful: OP question is tagged [c] not [c#]