How to Find the Maximum of Two Integers without Using Comparison Operator?

ACMer

9 years ago

This is a classic interview question: You are asked to write a function that returns a bigger number of both, without using any comparison operator, such as if, or ternary operator (e.g. ?).

1
2
3

int max(int a, int b) {
   // TODO
}

int max(int a, int b) {
   // TODO
}

This is to return (a > b ? a : b); If a is larger than b returns a otherwise b. We let $tex_eeb70ce17aa48a2c9aea4fffb4a36a46 How to Find the Maximum of Two Integers without Using Comparison Operator? c / c++ interview questions$ , thus if c is negative, the function returns b otherwise a.

$tex_ad96c237a79ccd93e2362d65d7333cf2 How to Find the Maximum of Two Integers without Using Comparison Operator? c / c++ interview questions$ if k = 0 and c is non-negative.
$tex_29c28e000600d0587e55872d02acddd4 How to Find the Maximum of Two Integers without Using Comparison Operator? c / c++ interview questions$ if k = 1 and c is negative.

So, the target is to compute the value of k, which is the MSB (most significant bit, the signed bit) of the integer c, negative means a smaller than b.

Thus, we have the following solution (bit right shift 31 positions and we have the signed bit at the right-most bit, the least significant bit (LSB)) :

inline int
max(int a, int b) {
  int c = a - b;
  int k = (c >> 31) & 1;
  return (a - k * c);
}

inline int
max(int a, int b) {
  int c = a - b;
  int k = (c >> 31) & 1;
  return (a - k * c);
}

–EOF (The Ultimate Computing & Technology Blog) —

331 words
Last Post: How to Find Out Whether a Machine is Big Endian or Little Endian in C/C++?
Next Post: Bit Manipulation: How to Set All Bits Between i and j in N equal to M?

The Permanent URL is: How to Find the Maximum of Two Integers without Using Comparison Operator? (AMP Version)

Related posts: