Cracking the coding interview--Q19.4
Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.
https://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/
Again,
X.
https://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/
http://www.geeksforgeeks.org/smallest-of-three-integers-without-comparison-operators/
int flip(int bit) {
return 1^bit;
}
/* Returns 1 if a is positive, and 0 if a is negative */
int sign(int a) {
return flip((a >> 31) & 0xl);
}
int getMaxNaive(int a, int b) {
int k = sign(a - b);
int q = flip(k);
return a * k + b * q;
}
int getMax(int a, int b) {
int c = a - b;
int sa = sign(a); // if a>= 0, then 1 else 0
int sb = sign(b); // if b >= 0, then 1 else 0
int sc= sign(c); // depends on whether or not a - b overflows
/* Goal: define a value k which is 1 if a> b and 0
* (if a = b, it doesn't matter what value k is) */
// If a and b have different 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); // opposite of k
return a * k + b * q;
}
Read full article from Cracking the coding interview--Q19.4
Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.
我们可以通过一步步的分析来将需要用到的if-else和比较操作符去掉：
If a > b, return a; else, return b.
If (a - b) < 0, return b; else, return a.
If (a - b) < 0, 令k = 1; else, 令k = 0. return a - k * (a - b).
令z = a - b. 令k是z的最高位，return a - k * z.
当a大于b的时候，a-b为正数，最高位为0，返回的a-k*z = a；当a小于b的时候， a-b为负数，最高位为1，返回的a-k*z = b。可以正确返回两数中较大的。
另外，k是z的最高位(0或1)，我们也可以用一个数组c来存a,b，然后返回c[k]即可。
X.https://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/
Here is a another solution which uses the fact that a number is stored in its 2’s complement form where the msb (most significant bit) is 0, if the number is positive, otherwise its 1.
int getMax(int a, int b) {
int c = a - b;
int k = (c >> 31) & 0x1;
int max = a - k * c;
return max;
}
Here, c stores the difference of a and b. Right shifting c by 31 times gives the msb of c; bit wise ANDing it with 1 results in 1 if
a < b, and 0 if a > bif a < b then, c < 0
i.e. msb of c is 1,
i.e k = 1
hence, max = a - (a - b) = bAgain,
if a > b then, c > 0
i.e. msb of c is 0
i.e.k = 0,
hence, max = aint Max1(int a, int b){
int c[2] = {
a, b
};
int z = a - b;
z = (z>>31) & 1;
return c[z];
}https://souvikpal.wordpress.com/2013/02/10/findmax-without-if-else/
Suppose A = 5, B = 10. Given two such integer number, you are required to find the maximum of them without using any if-else or other comparison operators.
The solution is straightforward. Consider a straight line with the two numbers as its end-points (refer to the picture above). Now the larger number, say Max, is away from their midpoint M by half the distance between the two endpoints. If d be the distance between A and B and M be the midpoint, then larger number
double getMaxMath(int a, int b) { return 0.5*(a+b + Math.abs(a-b));}double getMinMath(int a, int b) { return 0.5*(a+b - Math.abs(a-b));}
Or, if the abs() function is not allowed, just square (a-b) and then take the square-root of it:
1
2
3
4
5
6
7
| double getMaxMath(int a, int b) { return 0.5*(a+b + Math.sqrt(Math.pow((a-b),2)));}double getMinMath(int a, int b) { return 0.5*(a+b - Math.sqrt(Math.pow((a-b),2)));} |
int min(int x, int y){ return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));}/* Function to find minimum of 3 numbers x, y and z*/int smallest(int x, int y, int z){ return min(x, min(y, z));}
Let k equal the sign of a - b such that if a - b >= 0, then k is 1. Else, k
We can then implement the code as follows. Let q be the inverse of k.
/* Flips a 1 to a 0 and a 0 to a 1 */int flip(int bit) {
return 1^bit;
}
/* Returns 1 if a is positive, and 0 if a is negative */
int sign(int a) {
return flip((a >> 31) & 0xl);
}
int getMaxNaive(int a, int b) {
int k = sign(a - b);
int q = flip(k);
return a * k + b * q;
}
This code almost works. It fails, unfortunately, when a - b overflows. Suppose, for example, that a is
INT MAX - 2 and b is -15. In this case, a - b will be greater than INT MAX and will overflow, resulting in a negative value.
We can implement a solution to this problem by using the same approach. Our goal is to maintain the
condition where k is 1 when a > b. We will need to use more complex logic to accomplish this.
When does a - b overflow? It will overflow only when a is positive and b is negative, or the other way
around. It may be difficult to specially detect the overflow condition, but we can detect when a and b have different signs. Note that if a and b have different signs, then we want k to equal sign (a).
int getMax(int a, int b) {
int c = a - b;
int sa = sign(a); // if a>= 0, then 1 else 0
int sb = sign(b); // if b >= 0, then 1 else 0
int sc= sign(c); // depends on whether or not a - b overflows
/* Goal: define a value k which is 1 if a> b and 0
* (if a = b, it doesn't matter what value k is) */
// If a and b have different 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); // opposite of k
return a * k + b * q;
}
Read full article from Cracking the coding interview--Q19.4
