解释一下这个片段，它在不使用 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 appears to be straightforward - it stores the difference of a and b. This value is negative if a < b and is nonnegative otherwise. But 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 进行 AND 运算(除了最后一位之外，其二进制表示在所有地方都是 0)擦除所有高位，只给你最低位.由于c>>的最低位；31 是 c 的最高位，这将 c 的最高位读取为 0 或 1.由于最高位是 1 iff c 为 1，这是一种检查 c 是负 (1) 还是正 (0) 的方法.结合上面的推理，如果 a < k 是 1b 否则为 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 ，然后 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 .否则，如果 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屋！