解释此片段，该片段无需使用if-else或任何其他比较运算符就可以找到两个整数的最大值? [英] Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?

问题描述

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

Find the maximum of two numbers. You should not use if-else or any other comparison operator. I found this question on online bulletin board, so i thought i should ask in StackOverflow

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

EXAMPLE Input: 5, 10 Output: 10

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

I found this solution, can someone help me understand these lines of code

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

推荐答案

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的差值太大而不能容纳整数，这将导致不确定的行为-糟糕！因此，我们假设这里不会发生这种情况.

Let's dissect this. This first line seems like it out to be straightforward - it stores the difference of a and b. This value is negative if a < b and is nonnegative otherwise. There's actually a bug here - if the difference of the numbers a and b is so big that it can't fit into an integer, this will lead to undefined behavior - oops! So let's assume that doesn't happen here.

在下一行是

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

这个想法是要检查c的值是否为负.实际上，在几乎所有现代计算机中，数字都是以二进制补码的格式存储的，如果数字为正，则数字的最高位为0，如果数字为负，则数字的最高位为1.此外，大多数整数都是32位. (c >> 31)将数字下移31位，将数字中的最高位留在最低位.取该数字并将其与1(其二进制表示除最后一位以外的所有地方均为0)进行下一步的操作将擦除所有较高的位，并为您提供最低的位.由于c >> 31的最低位是c的最高位，因此这会读取c的最高位为0或1.由于最高位是1，而c是1，因此这是一种方法检查c是负数(1)还是正数(0).将此推理与上述内容相结合，如果a < b，则k为1，否则为0.

the idea is to check if the value of c is negative. In virtually all modern computers, numbers are stored in a format called two's complement in which the highest bit of the number is 0 if the number is positive and 1 if the number is negative. Moreover, most ints are 32 bits. (c >> 31) shifts the number down 31 bits, leaving the highest bit of the number in the spot for the lowest bit. The next step of taking this number and ANDing it with 1 (whose binary representation is 0 everywhere except the last bit) erases all the higher bits and just gives you the lowest bit. Since the lowest bit of c >> 31 is the highest bit of c, this reads the highest bit of c as either 0 or 1. Since the highest bit is 1 iff c is 1, this is a way of checking whether c is negative (1) or positive (0). Combining this reasoning with the above, k is 1 if a < b and is 0 otherwise.

最后一步是这样做:

int max = a - k * c;

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

If a < b, then k == 1 and k * c = c = a - b, and so

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

从a < b开始，这是正确的最大值.否则，如果为a >= b，则为k == 0和

Which is the correct max, since a < b. Otherwise, if a >= b, then k == 0 and

a - k * c = a - 0 = a

这也是正确的最大值.

这篇关于解释此片段，该片段无需使用if-else或任何其他比较运算符就可以找到两个整数的最大值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！