面试题 16.07. 最大数值 ——一种基于乘法和位运算的解题思路

剧透警告,没写过的勿触

题目:

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

qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq

qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq

qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq

qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq pwq qwq qwq qwq qwq qwq qwq qwq qwq qwq

qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq qwq

先上代码:

class Solution {
    public int maximum(int a, int b) {
        int isNegative = (a / 2 - b / 2) >>> 31;
        return ((1 - isNegative) * a) + (isNegative * b);
    }
}

因为0乘任何数都是0,结果一个0一个1,就可以把乘积相加咯qwq
硬要说问题的话,小数不能使用>>> 31的方式取1(好像是8+23的原因?),比如:0.2 - 0.8 == -0.6000000000000001,解决方式的话可以使用isNegative = (isNegative * 2) | 1来变回正整数。当然,题目的数据集都是整数,而且也恰巧差值都大于1(如果遇到差值为1的样本,那就会报错了),所以* 2只是复原了这个方法/ 2的结果。

加上优化写了四个小时,尝试了四种思路:

  • 使用与、非、异或符号加位运算的数学运算思路
  • 使用try catch和0不能被除的报错
  • 使用数组和布尔值实现减法器
  • 最终方案,上面的代码

当然前两条已经尝试无果了,位运算根本无法摘取出他们的最大值差异,所以就陷入了死循环;至于try catch?开玩笑一样的方法,直接不给过= =

然后是数组和布尔的,上代码:


class Solution {
    public int maximum(int a, int b) {
        int[] res = new int[]{a, b};
        return res[(a / 2 - b / 2) >>> 31];
    }
}

也是从汇编减法器中迸发的想法,一瞬间醍醐灌顶。

然后呢,后面两个解法差不多半小时全部写完awa

后面两个代码的想法来自朋友写的一个公式,产生了火花,感谢朱静Think的帮助:

图里内容抽象出来就是:
如果|a - b| + (b - a) = 0,则说明a > b,这很重要,是扭转战局的胜负手。

热门相关:冉冉心动   花月颂   锦乡里   民国之文豪崛起   年轻的妈妈2