A few days ago I attempted to solve a getMax coding problem that required no branching but was unable to. This post is me trying to understand how to arrive at the solution using bitwise operations.

The following solution is from https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

    /*Function to find maximum of x and y*/
    static int max(int x, int y)
    {
      return x ^ ((x ^ y) & -(x < y));
    }

Problem

We need an equation that produces either X or Y

Some mathematical proofs involve adding values to an equation that have no direct effect. In this case we know that XOR with two equal values will have no effect. So the equations can be re-written

    x = x

    ( y XOR y ) XOR x = x

and in terms of y

    y = y

    ( x XOR x ) XOR y = y

Again, it is common in mathematical proofs to re-arrange the equation or view the equation in a different perspective. In this case if we were to represent one of the equations with the other variable, we would get -

    x XOR (x XOR y) = y

We have moved the brackets around above. But it becomes evident that if the value inside the bracket was zero, the answer would change to x instead of y, because XOR with zero will return that number

In bit operations, it is common to AND a number with zero in order to get a zero

But that zero has to be generated - and can be generated from the original problem.

Is Y greater than X ?

If False we get a zero, and therefore the answer we are looking for X.
If True we get Y.

Note

The Solution negates the comparator to ensure that all bits are set to 1 in the case of -1

Jason Coelho

Get Max using bit operations

Problem

Note