题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例：

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

题目思考

1. 如何代替比较和条件操作?
2. 需要考虑什么边界情况?

解决方案

思路

• 这道题目乍一看无从下手, 如何不使用比较/条件操作来判断大小呢?
• 我们可以换个思路, 根据 a-b 的正负来判断: a>=b 时 a-b 是非负数, 否则是负数
• 也就是说: a-b>=0 时, a-b 的符号位是 0; a-b<0 时, a-b 的符号位是 1
• 得到符号位后, 我们可以利用乘法, 得到较大的数: 较大的数需要乘以 1, 而较小的数乘以 0
• 使用公式表示, 就是(1-neg)*a+neg*b (neg 是 a-b 的符号位)
• 特别注意, 两个数字的减法可能导致 32 位有符号数字存不下, 例如 0x7fffffff-(-1), 此时第 32 位不再是符号位, 更高位才是
• 所以符号位使用 a-b 右移至少 32 位得出 (更高位数的符号位和 32 位一样, 都是正数为 0, 负数为 1)
• python 的话由于数字是动态类型, 所以无需转换; 而其他语言, 例如 Go/Java, 则需要先将数字转成 64 位类型, 再右移 32 位得到符号位

复杂度

• 时间复杂度 O(1): 只进行了几次常数时间的位运算操作
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def maximum(self, a: int, b: int) -> int:
        # 注意减法可能导致32位有符号数字存不下, 例如0x7fffffff-(-1), 此时第32位不再是符号位, 更高位才是
        # 所以这里右移32而不是31, 从而得到正确的符号位
        neg = ((a - b) >> 32) & 1
        return (1 - neg) * a + neg * b

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊