### Problem

Write a method which finds the maximum of two numbers You should not use if-else or any other comparison operator

EXAMPLE

Input: 5, 10

Output: 10

### Solution

**Method 1 - Using arithematic operator**

Let a is greater than b, and M is the mid point, then:

then

max = (a + b) / 2 + |a - b| / 2

**Method 2 - Using most significant bit**

Let’s try to solve this by “re-wording” the problem We will re-word the problem until we get something that has removed all if statements

Rewording 1: If a > b, return a; else, return b

Rewording 2: If (a – b) is negative, return b; else, return a

Rewording 3: If (a – b) is negative, let k = 1; else, let k = 0. Return a – k * (a – b)

Rewording 4: Let c = a – b. Let k = the most significant bit of c. Return a – k * c

We have now reworded the problem into something that fits the requirements for this is below:

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

What is the significance of :

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

It tells us the sign of the c i.e. a-b. So, we do following

max = a - k *(a-b)

`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`

__Assumptions__

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.What if want min of 2 numbers without comparison operator?

Answer to this is again similar to above.

Using method 1, we will have

min = (a+b)/2 - |a-b|/2

Similarly using method 2, gives us:

c = a - b; k = (c >> 31) & 0x1; max = b+ k*c

## What if want to find the min of 3 numbers without using comparison operator?

Answer is simple,min(a,b,c) = min(a,min(b,c))Similarly for max.

Please let me know if you have other suggestions.

**References**

- http://tianrunhe.wordpress.com/2012/05/14/find-the-maximum-of-two-numbers-without-use-of-comparison-operators-or-if-else/
- http://stackoverflow.com/questions/4772780/find-the-maximum-of-two-numbers-without-using-if-else-or-any-other-comparison-op
- http://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/

## 0 comments:

## Post a Comment