Loading…

Finding the maximum of two numbers

 

The most widespread option of max function implementation is to check the operator of the a-b expression. In this case, we cannot use comparisons operators, but we can use the multiplication operator.

 

Note

The task’s essence is to make everything without switch instructions at the processor level instead of hiding the comparison or condition in a certain standard function like abs() or a standard operator like integer division. 

 

Let’s indicate the a-b expression operator as k. If a – b >= 0, then k = 1, otherwise k = 0. Let q be a k reverse value.

 

The code will be as follows:

 

/ * Reflect 1 to 0 and 0 to 1 * / int flip (int bit) {return 1 ^ bit; } / * Return 1 if the number is positive, and 0 if it is negative * / int sign (int a) {return flip ((a >> (sizeof (int) * CHAR_BIT – 1)))) & 0x1); } int getMaxNaive (int a, int b) {int k = sign (a – b); int q = flip (k); return a * k + b * q; }

 

This is almost workable code. You face the problems when overflowing. Let’s assume that a = INT_MAX – 2 and b = -15. In this case, a – b will stop being transferred to INT_MAX and will call an overflow (the value will become negative).

 

You can use the same approach, but you need to come up with another implementation. You need to reach the k = 1 condition fulfilment when a > b. In order to reach this, you need to use a more complicated logic.

 

When the a – b overflow emerges? It only emerges when a is positive and b is negative (or vice versa). It is pretty tough to detect the overflow, but we can understand that a and b have different operators. In case a and b have different operators, then let k = sign(a).

 

The logic will be the following:

 

1. In case a and b have different operators:

// if a> 0, then b <0 and k = 1.

// if a <0, then b> 0 and k = 0.

// one way or another, k = sign (a)

 

2. Let k = sign(a)

3. Otherwise, let k = sign(a – b) // an overflow is impossible

 

The code below implements this algorithm using multiplication instead of comparison operators:

 

int getMax (int a, int b) {int c = a – b; int sa = sign (a); // if a> = 0, then 1, otherwise 0 int sb = sign (b); // if a> = 1, then 1, otherwise 0 int sc = sign (c); // depends on overflow a – b / * Purpose: find k, which = 1 if a> b, and 0 if a <b. * if a = b, k does not matter * / // If a and b have equal signs, then k = sign (a) int use_sign_of_a = sa ^ sb; // If a and b have the same sign, then k = sign (a – b) int use_sign_of_c = flip (sa ^ sb); int k = use_sign_of_a * sa + use_sign_of_c * sc; int q = flip (k); // reflection k return a * k + b * q; }

 

We should note we divide the code into methods and introduce variables for your guidance. This is not the most compact or efficient way to write code, but this way we make the code clearer.

 


Leave a Comment