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;  
}

Answer 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.

Answer 2

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

Answer 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

Answer 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

Answer 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);
}

Answer 6

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

This solution avoids multiplication. m will either be 0x00000000 or 0xffffffff

Answer 7

Here's how I think I'd do the job. It's not as readable as you might like, but when you start with "how do I do X without using the obvious way of doing X, you have to kind of expect that. In theory, this gives up some portability too, but you'd have to find a pretty unusual system to see a problem.

#define BITS (CHAR_BIT * sizeof(int) - 1)

int findmax(int a, int b) { 
    int rets[] = {a, b};
    return rets[unsigned(a-b)>>BITS];
}

This does have some advantages over the one shown in the question. First of all, it calculates the correct size of shift, instead of being hard-coded for 32-bit ints. Second, with most compilers we can expect all the multiplication to happen at compile time, so all that's left at run time is trivial bit manipulation (subtract and shift) followed by a load and return. In short, this is almost certain to be pretty fast, even on the smallest microcontroller, where the original used multiplication that had to happen at run-time, so while it's probably pretty fast on a desktop machine, it'll often be quite a bit slower on a small microcontroller.

Answer 8

Using the shifting idea to extract the sign as posted by others, here's another way:

max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]

This pushes the two numbers into an array with the maximum number given by the array-element whose index is sign bit of the difference between the two numbers.

Do note that:

1. The difference (a - b) may overflow.
2. If the numbers are unsigned and the >> operator refers to a logical right-shift, the & 1 is unnecessary.

Answer 9

Here's what those lines are doing:

c is a-b. if c is negative, a<b.

k is 32nd bit of c which is the sign bit of c (assuming 32 bit integers. If done on a platform with 64 bit integers, this code will not work). It's shifted 31 bits to the right to remove the rightmost 31 bits leaving the sign bit in the right most place and then anding it with 1 to remove all the bits to the left (which will be filled with 1s if c is negative). So k will be 1 if c is negative and 0 if c is positive.

Then max = a - k * c. If c is 0, this means a>=b, so max is a - 0 * c = a. If c is 1, this means that a<b and then a - 1 * c = a - (a - b) = a - a + b = b.

In the overall, it's just using the sign bit of the difference to avoid using greater than or less than operations. It's honestly a little silly to say that this code doesn't use a comparison. c is the result of comparing a and b. The code just doesn't use a comparison operator. You could do a similar thing in many assembly codes by just subtracting the numbers and then jumping based on the values set in the status register.

I should also add that all of these solutions are assuming that the two numbers are integers. If they are floats, doubles, or something more complicated (BigInts, Rational numbers, etc.) then you really have to use a comparison operator. Bit-tricks will not generally do for those.

Answer 10

getMax() Function Without Any Logical Operation-

int getMax(int a, int b){
    return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2;
}

---

Explanation:

Lets smash the 'max' into pieces,

max
= ( max + max ) / 2
= ( max + (min+differenceOfMaxMin) ) / 2
= ( max + min + differenceOfMaxMin ) / 2
= ( max + min + | max - min | ) ) / 2

So the function should look like this-

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2

Now,

absolute(x)
= x [if 'x' is positive] or -x [if 'x' is negative]
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )

In integer positive number the first bit (sign bit) is- 0; in negative it is- 1. By shifting bits to the right (>>) the first bit can be captured.

During right shift the empty space is filled by the sign bit. So 01110001 >> 2 = 00011100, while 10110001 >> 2 = 11101100.

As a result, for 8 bit number shifting 7 bit will either produce- 1 1 1 1 1 1 1 [0 or 1] for negative, or 0 0 0 0 0 0 0 [0 or 1] for positive.

Now, if OR operation is performed with 00000001 (= 1), negative number yields- 11111111 (= -1), and positive- 00000001 (= 1).

So,

absolute(x)
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
= x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 )
= x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 )
= x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )

Finally,

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2

---

Another way-

int getMax(int a, int b){
    int i[] = {a, b};
    return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ];
}

Answer 11

static int mymax(int a, int b)

    {
        int[] arr;
        arr = new int[3];
        arr[0] = b;
        arr[1] = a;
        arr[2] = a;
        return arr[Math.Sign(a - b) + 1];

    }

If b > a then (a-b) will be negative, sign will return -1, by adding 1 we get index 0 which is b, if b=a then a-b will be 0, +1 will give 1 index so it does not matter if we are returning a or b, when a > b then a-b will be positive and sign will return 1, adding 1 we get index 2 where a is stored.

Answer 12

The code which I am providing is for finding maximum between two numbers, the numbers can be of any data type(integer, floating). If the input numbers are equal then the function returns the number.

double findmax(double a, double b)
{
    //find the difference of the two numbers
    double diff=a-b;
    double temp_diff=diff;
    int int_diff=temp_diff;
    /*
      For the floating point numbers the difference contains decimal
      values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need
      to get a non-zero number on the left side of '.'
    */
    while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) )
    {
       temp_diff = temp_diff * 10;
       int_diff = temp_diff;
    }
    /*
      shift the sign bit of variable 'int_diff' to the LSB position and find if it is 
      1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of
      the two numbers (variable 'diff') then subtract it with the variable a.
    */
    return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 ));
}

Description

• The first thing the function takes the arguments as double and has return type as double. The reason for this is that to create a single function which can find maximum for all types. When integer type numbers are provided or one is an integer and other is the floating point then also due to implicit conversion the function can be used to find the max for integers also.
• The basic logic is simple, let's say we have two numbers a & b if a-b>0(i.e. the difference is positive) then a is maximum else if a-b==0 then both are equal and if a-b<0(i.e. diff is -ve) b is maximum.

• The sign bit is saved as the Most Significant Bit(MSB) in the memory. If MSB is 1 and vice-versa. To check if MSB is 1 or 0 we shift the MSB to the LSB position and Bitwise & with 1, if the result is 1 then the number is -ve else no. is +ve. This result is obtained by the statement:

  int_diff >> (sizeof(int) * 8 - 1 ) & 1

Here to get the sign bit from the MSB to LSB we right shift it to k-1 bits(where k is the number of bits needed to save an integer number in the memory which depends on the type of system). Here k= sizeof(int) * 8 as sizeof() gives the number of bytes needed to save an integer to get no. of bits, we multiply it with 8. After the right shift, we apply the bitwise & with 1 to get the result.

• Now after obtaining the result(let us assume it as r) as 1(for -ve diff) and 0(for +ve diff) we multiply the result with the difference of the two numbers, the logic is given as follows:

  1. if a>b then a-b>0 i.e., is +ve so the result is 0(i.e., r=0). So a-(a-b)*r => a-(a-b)*0, which gives 'a' as the maximum.
  2. if a < b then a-b<0 i.e., is -ve so the result is 1(i.e., r=1). So a-(a-b)*r => a-(a-b)*1 => a-a+b =>b , which gives 'b' as the maximum.

• Now there are two remaining points 1. the use of while loop and 2. why I have used the variable 'int_diff' as an integer. To answer these properly we have to understand some points:

  1. Floating type values cannot be used as an operand for the bitwise operators.
  2. Due to above reason, we need to get the value in an integer value to get the sign of difference by using bitwise operators. These two points describe the need of variable 'int_diff' as integer type.
  3. Now let's say we find the difference in variable 'diff' now there are 3 possibilities for the values of 'diff' irrespective of the sign of these values. (a). |diff|>=1 , (b). 0<|diff|<1 , (c). |diff|==0.
  4. When we assign a double value to integer variable the decimal part is lost.
  5. For case(a) the value of 'int_diff' >0 (i.e.,1,2,...). For other two cases int_diff=0.
  6. The condition (temp_diff-int_diff)||0.0 checks if diff==0 so both numbers are equal.
  7. If diff!=0 then we check if int_diff|0 is true i.e., case(b) is true
  8. In the while loop, we try to get the value of int_diff as non-zero so that the value of int_diff also gets the sign of diff.

Answer 13

#include<stdio.h>
main()
{
        int num1,num2,diff;
        printf("Enter number 1 : ");
        scanf("%d",&num1);
        printf("Enter number 2 : ");
        scanf("%d",&num2);
        diff=num1-num2;
        num1=abs(diff);
        num2=num1+diff;
        if(num1==num2)
                printf("Both number are equal\n");
        else if(num2==0)
                printf("Num2 > Num1\n");
        else
                printf("Num1 > Num2\n");
}

Answer 14

Here are a couple of bit-twiddling methods to get the max of two integral values:

Method 1

int max1(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return (a & ~mask) | (b & mask);
}

Explanation:

• (a - b) >> SIGN_BIT_SHIFT - If a > b then a - b is positive, thus the sign bit is 0, and the mask is 0x00.00. Otherwise, a < b so a - b is negative, the sign bit is 1 and after shifting, we get a mask of 0xFF..FF
• (a & ~mask) - If the mask is 0xFF..FF, then ~mask is 0x00..00 and then this value is 0. Otherwise, ~mask is 0xFF..FF and the value is a
• (b & mask) - If the mask is 0xFF..FF, then this value is b. Otherwise, mask is 0x00..00 and the value is 0.

Finally:

• If a >= b then a - b is positive, we get max = a | 0 = a
• If a < b then a - b is negative, we get max = 0 | b = b

Method 2

int max2(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return a ^ ((a ^ b) & mask);
}

Explanation:

• Mask explanation is the same as for Method 1. If a > b the mask is 0x00..00, otherwise the mask is 0xFF..FF
• If the mask is 0x00..00, then (a ^ b) & mask is 0x00..00
• If the mask is 0xFF..FF, then (a ^ b) & mask is a ^ b

Finally:

• If a >= b, we get a ^ 0x00..00 = a
• If a < b, we get a ^ a ^ b = b

Answer 15

//In C# you can use math library to perform min or max function

using System;

class NumberComparator {

static void Main()
{

    Console.Write(" write the first number to compare: ");
    double first_Number = double.Parse(Console.ReadLine());

    Console.Write(" write the second number to compare: ");
    double second_Number = double.Parse(Console.ReadLine());

    double compare_Numbers = Math.Max(first_Number, second_Number);
    Console.Write("{0} is greater",compare_Numbers);

}

}

Answer 16

No logical operators, no libs (JS)

function (x, y) {
    let z = (x - y) ** 2;
    z = z ** .5;
    return (x + y + z) / 2
}

Answer 17

The logic described in a problem can be explained as if 1st number is smaller then 0 will be subtracted else difference will be subtracted from 1st number to get 2nd number. I found one more mathematical solution which I think is bit simpler to understand this concept.

Considering a and b as given numbers

c=|a/b|+1;
d=(c-1)/b;
smallest number= a - d*(a-b);

Again,The idea is to find k which is wither 0 or 1 and multiply it with difference of two numbers.And finally this number should be subtracted from 1st number to yield the smaller of the two numbers. P.S. this solution will fail in case 2nd number is zero

Answer 18

int a=151;
int b=121;
int k=Math.abs(a-b);
int j= a+b;
double k1=(double)(k);
double j1= (double) (j);
double c=Math.ceil(k1/2) + Math.floor(j1/2);
int c1= (int) (c);
System.out.println(" Max value = " + c1);

Answer 19

There is one way

 public static int Min(int a, int b)
  {
   int dif = (int)(((uint)(a - b)) >> 31);
   return a * dif + b * (1 - dif);
  }

and one

return (a>=b)?b:a;