Cracking the coding interview--Q19.4

February 21, 2013
作者:Hawstein
出处:http://hawstein.com/posts/19.4.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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

译文:

写一个函数返回两个数中的较大者,你不能使用if-else及任何比较操作符。

解答

我们可以通过一步步的分析来将需要用到的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]即可。

代码如下:

#include <iostream>
using namespace std;

int Max1(int a, int b){
    int c[2] = {
        a, b
    };
    int z = a - b;
    z = (z>>31) & 1;
    return c[z];
}
int Max2(int a, int b){
    int z = a - b;
    int k = (z>>31) & 1;
    return a - k * z;
}
int main(){
    int a = 5, b = 10;
    cout<<Max1(a, b)<<endl;
    cout<<Max2(a, b)<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview