一尘不染

解释此片段,该片段不使用if-else或任何其他比较运算符就可以找到两个整数的最大值?

algorithm

查找两个数字的最大值。您不应使用if-else或任何其他比较运算符。我在在线公告板上发现了这个问题,所以我认为我应该在StackOverflow中询问

示例输入:5、10输出:10

我找到了这个解决方案,有人可以帮我理解这些代码行吗

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}

阅读 245

收藏
2020-07-28

共1个答案

一尘不染

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

让我们对此进行剖析。第一行看起来很简单-它存储了a和的差b。如果为负,则该值为a < b负;否则为非负。其实这里有一个错误-
如果数字的差异a,并b是如此之大,它不适合到一个整数,这将导致不确定的行为-哎呀!因此,我们假设这里不会发生这种情况。

在下一行中

int k = (c >> 31) & 0x1;

想法是检查的值是否c为负。在几乎所有现代计算机中,数字都是以 二进制补码
的格式存储的,如果数字为正,则数字的最高位为0,如果数字为负,则数字的最高位为1。此外,大多数整数都是32位。 (c >> 31)将数字向下移动31位,将数字的最高位保留在最低位。取该数字并将其与1(其二进制表示除最后一位以外的所有地方均为0)进行下一步的操作将擦除所有较高位,并为您提供最低位。由于的最低位`c

31是的最高位c,因此读取的最高位c为0或1。由于最高位是1,当iffc为1时,这是一种检查是否为c是负数(1)还是正数(0)。将此推理与上述内容结合使用,k如果为1 ,则为1a < b`,否则为0。

最后一步是这样做:

int max = a - k * c;

如果a < b,则k == 1k * c = c = a - b,依此类推

a - k * c = a - (a - b) = a - a + b = b

自以来,这是正确的最大值a < b。否则,如果a >= b,则k == 0

a - k * c = a - 0 = a

这也是正确的最高

2020-07-28