面试题 16.07. 最大数值

Posted on | In
Words count in article: 277 | Reading time ≈ 1

题目

编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

示例 1:

1
2
输入： a = 1, b = 2
输出： 2

解法

解法一：

同号相减永不溢出，异号相比无脑选正。

JAVA

1
2
3
4
5
6
7
8
9
10
11
public int maximum(int a, int b) {
        // 先考虑没有溢出时的情况，计算 b - a 的最高位，依照题目所给提示 k = 1 时 a > b，即 b - a 为负
        int k = b - a >>> 31;
        // 再考虑 a b 异号的情况，此时无脑选是正号的数字
        int aSign = a >>> 31, bSign = b >>> 31;
        // diff = 0 时同号，diff = 1 时异号
        int diff = aSign ^ bSign;
        // 在异号，即 diff = 1 时，使之前算出的 k 无效，只考虑两个数字的正负关系
        k = k & (diff ^ 1) | bSign & diff;
        return a * k + b * (k ^ 1);
    }

解法二：

平均值法

max(a, b) = ((a + b) + abs(a - b)) / 2。

1
2
3
4
5
6
int maximum(int a, int b) {
        long _sum = long(a) + long(b);
        long _diff = long(a) - long(b);
        long _abs_diff = (_diff ^ (_diff >> 63)) - (_diff >> 63);
        return (_sum + _abs_diff) / 2;
    }

参考资料

题解1

题解2

0%