Sunday, April 15, 2012

Find the Maximum of Two Integers without Comparison

Problem: Given two integers a and b, find the bigger one between them without using comparison (e.g., "if" statement).

Solution: Here we need a little bit "bit" operation. We know, if a-b>=0, max(a,b) = a; otherwise, max(a,b) = a - (a-b). Then you may understand the following hack:

int max(int a, int b)
{
   int c = a-b;

   //assume integer has 4 bytes, by shifting c 
   //rightward, what we get is the sign bit
   //(that indicate if c is negative or not
   int k = c >> 31;

   return  a - k*c;

}


2 comments:

  1. How about this solution

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

    ReplyDelete
  2. Thanks Tristan, another good one right here:

    Find maximum without comparison

    ReplyDelete