[CareerCup] 17.4 Maximum of Two Numbers 两数中的较大值

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

这道题让我们找出两个数中的较大值,不能用if..else..语句判断,也不能用任何比较符号。那么我们怎么办呢,我们看两个数的差值a-b是否大于0,如果大于0,说明a大,如果小于0,说明b大。然后我们用一个变量k来记录a-b的符号位,用q来表示k的相反数,这样当a大的时候,k=1, q=0,反之当b大的时候,k=0,q=1,那么我们只要用a*k + b*q就能得到较大数了:

int flip(int bit) {
return ^ bit;
} int sign(int a) {
return flip((a >> ) & 0x1);
} int getMaxNaive(int a, int b) {
int k = sign(a - b);
int q = flip(k);
return a * k + b * q;
}

但是上面的解法有时候会有问题,比如当a=INT_MAX-2, b = -15的时候,a-b就会溢出,那么我们怎么办呢?溢出的情况只会发生在当a是正数,而b是负数的时候,或者反回来的情况,也就是说a和b符号不同。那么我们让k = sign(a),逻辑如下:

当a和b的符号不同,k = sign(a)

否则,k = sign(a - b)

那么我们可以分别保存a,b和a-b的符号,然后我们判断a和b的符号是否相同,如果不相同我们用a的符号,如果相同,我们用a-b的符号,这样我们就可以避免溢出得到正确的k,之后就跟上面的方法完全一样了:

int getMax(int a, int b) {
int c = a - b;
int sa = sign(a), sb = sign(b), sc = sign(c);
int m = sa ^ sb, n = flip(sa ^ sb);
int k = m * sa + n * sc, q = flip(k);
return a * k + b * q;
}

CareerCup All in One 题目汇总

上一篇:unix网络编程str_cli使用epoll实现


下一篇:windows核心编程---第六章 线程的调度