C语言 解释一下这个片段，它在不使用 if-else 或任何其他比较运算符的情况下找到两个整数的最大值？

Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?

提问by SuperMan

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

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

EXAMPLE Input: 5, 10 Output: 10

示例输入：5, 10 输出：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;  
}

回答by templatetypedef

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

Let's dissect this. This first line seems like it out to be straightforward - it stores the difference of aand b. This value is negative if a < band is nonnegative otherwise. There's actually a bug here - if the difference of the numbers aand bis 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.

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

In the next line, which is

在下一行，这是

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

the idea is to check if the value of cis negative. In virtually all modern computers, numbers are stored in a format called two's complementin 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 >> 31is the highest bit of c, this reads the highest bit of cas either 0 or 1. Since the highest bit is 1 iff cis 1, this is a way of checking whether cis negative (1) or positive (0). Combining this reasoning with the above, kis 1 if a < band is 0 otherwise.

这个想法是检查值是否c为负。在几乎所有现代计算机中，数字都以一种称为二进制补码的格式存储，其中数字的最高位是 0，如果是正数，而 1 是负数。此外，大多数整数是 32 位。 (c >> 31)将数字向下移动 31 位，将数字的最高位保留在最低位。下一步将这个数字与 1 进行 AND 运算（除了最后一位之外，其二进制表示在所有地方都是 0）擦除所有高位，只给你最低位。由于 的最低位c >> 31是 的最高位c，因此将 的最高位读取c为 0 或 1。由于最高位是 1 iffc为 1，这是一种检查是否c为负 (1) 或正 (0)。将此推理与上述推理相结合，k如果为 1 a < b，则为 0，否则为 0。

The final step is to do this:

最后一步是这样做：

int max = a - k * c;

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

如果a < b，那么k == 1和k * c = c = a - b，等

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

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

哪个是正确的最大值，因为a < b。否则，如果a >= b，则k == 0和

a - k * c = a - 0 = a

Which is also the correct max.

这也是正确的最大值。

回答by mike.dld

Here we go: (a + b) / 2 + |a - b| / 2

开始了： (a + b) / 2 + |a - b| / 2

回答by Prasoon Saurav

Use bitwise hacks

使用按位技巧

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

If you know that INT_MIN <= x - y <= INT_MAX,then you can use the following, which is faster because (x - y)only needs to be evaluated once.

如果您知道，INT_MIN <= x - y <= INT_MAX,那么您可以使用以下方法，它会更快，因为(x - y)只需要评估一次。

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

Source : Bit Twiddling Hacks by Sean Eron Anderson

资料来源：Sean Eron Anderson 的 Bit Twiddling Hacks

回答by CashCow

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

This is based on the same technique as mike.dld's solution, but it is less "obvious" here what I am doing. An "abs" operation looks like you are comparing the sign of something but I here am taking advantage of the fact that sqrt() will always return you the positive square root so I am squaring (a-b) writing it out in full then square-rooting it again, adding a+b and dividing by 2.

这基于与mike.dld 的解决方案相同的技术，但在这里我正在做的事情不那么“明显”。“abs”操作看起来像是在比较某事物的符号，但我在这里利用了一个事实，即 sqrt() 将始终返回正平方根，因此我将平方 (ab) 完整地写出来，然后平方-再次生根，添加 a+b 并除以 2。

You will see it always works: eg the user's example of 10 and 5 you get sqrt(100 + 25 - 100) = 5 then add 10 and 5 gives you 20 and divide by 2 gives you 10.

您会看到它始终有效：例如，用户的 10 和 5 示例得到 sqrt(100 + 25 - 100) = 5 然后加上 10 和 5 得到 20，除以 2 得到 10。

If we use 9 and 11 as our numbers we would get (sqrt(121 + 81 - 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11

如果我们使用 9 和 11 作为我们的数字，我们将得到 (sqrt(121 + 81 - 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11

回答by novice

The simplest answer is below.

最简单的答案如下。

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}

回答by vikky.rk

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

This solution avoids multiplication. m will either be 0x00000000 or 0xffffffff

此解决方案避免了乘法。m 将是 0x00000000 或 0xffffffff

回答by Ani

Using the shifting idea to extract the sign as posted by others, here's another way:

使用转移的想法来提取其他人发布的标志，这是另一种方式：

max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]

This pushes the two numbers into an array with the maximum number given by the array-element whose index is sign bit of the difference between the two numbers.

这会将两个数字推入一个数组，该数组的最大数字由数组元素给出，该元素的索引是两个数字之间差异的符号位。

Do note that:

请注意：

1. The difference (a - b) may overflow.
2. If the numbers are unsigned and the >>operator refers to a logicalright-shift, the & 1is unnecessary.

1. 差异(a - b) 可能会溢出。
2. 如果数字是无符号的并且>>运算符指的是逻辑右移，& 1则不需要。

回答by Jerry Coffin

Here's how I think I'd do the job. It's not as readable as you might like, but when you start with "how do I do X without using the obvious way of doing X, you have to kind of expect that. In theory, this gives up some portability too, but you'd have to find a pretty unusual system to see a problem.

这就是我认为我会做这项工作的方式。它并不像您希望的那样可读，但是当您从“如何在不使用明显的 X 方法的情况下执行 X 时，您必须有点期待。理论上，这也放弃了一些可移植性，但是您”必须找到一个非常不寻常的系统才能看到问题。

#define BITS (CHAR_BIT * sizeof(int) - 1)

int findmax(int a, int b) { 
    int rets[] = {a, b};
    return rets[unsigned(a-b)>>BITS];
}

This does have some advantages over the one shown in the question. First of all, it calculates the correct size of shift, instead of being hard-coded for 32-bit ints. Second, with most compilers we can expect all the multiplication to happen at compile time, so all that's left at run time is trivial bit manipulation (subtract and shift) followed by a load and return. In short, this is almost certain to be pretty fast, even on the smallest microcontroller, where the original used multiplication that had to happen at run-time, so while it's probably pretty fast on a desktop machine, it'll often be quite a bit slower on a small microcontroller.

这确实比问题中显示的有一些优势。首先，它计算正确的移位大小，而不是针对 32 位整数进行硬编码。其次，对于大多数编译器，我们可以预期所有的乘法都在编译时发生，所以在运行时剩下的就是微不足道的位操作（减法和移位），然后是加载和返回。简而言之，这几乎肯定会非常快，即使在最小的微控制器上，原始使用的乘法必须在运行时发生，因此虽然它在台式机上可能非常快，但通常会相当在小型微控制器上慢一点。

回答by Keith Irwin

Here's what those lines are doing:

以下是这些行的作用：

c is a-b. if c is negative, a<b.

c 是 ab。如果 c 为负，则 a<b。

k is 32nd bit of c which is the sign bit of c (assuming 32 bit integers. If done on a platform with 64 bit integers, this code will not work). It's shifted 31 bits to the right to remove the rightmost 31 bits leaving the sign bit in the right most place and then anding it with 1 to remove all the bits to the left (which will be filled with 1s if c is negative). So k will be 1 if c is negative and 0 if c is positive.

k 是 c 的第 32 位，它是 c 的符号位（假设是 32 位整数。如果在具有 64 位整数的平台上完成，此代码将不起作用）。它向右移动 31 位以删除最右边的 31 位，将符号位留在最右边的位置，然后与 1 相加以删除左边的所有位（如果 c 为负，则用 1 填充）。因此，如果 c 为负，则 k 将为 1，如果 c 为正，则 k 将为 0。

Then max = a - k * c. If c is 0, this means a>=b, so max is a - 0 * c = a. If c is 1, this means that a<b and then a - 1 * c = a - (a - b) = a - a + b = b.

然后 max = a - k * c。如果 c 是 0，这意味着 a>=b，所以 max 是 a - 0 * c = a。如果 c 是 1，这意味着 a<b，然后 a - 1 * c = a - (a - b) = a - a + b = b。

In the overall, it's just using the sign bit of the difference to avoid using greater than or less than operations. It's honestly a little silly to say that this code doesn't use a comparison. c is the result of comparing a and b. The code just doesn't use a comparison operator. You could do a similar thing in many assembly codes by just subtracting the numbers and then jumping based on the values set in the status register.

总的来说，它只是使用差的符号位来避免使用大于或小于操作。说这段代码不使用比较，老实说有点傻。c 是比较 a 和 b 的结果。代码只是不使用比较运算符。你可以在许多汇编代码中做类似的事情，只需减去数字，然后根据状态寄存器中设置的值跳转。

I should also add that all of these solutions are assuming that the two numbers are integers. If they are floats, doubles, or something more complicated (BigInts, Rational numbers, etc.) then you really have to use a comparison operator. Bit-tricks will not generally do for those.

我还应该补充一点，所有这些解决方案都假设这两个数字是整数。如果它们是浮点数、双精度数或更复杂的东西（BigInts、有理数等），那么您真的必须使用比较运算符。位技巧通常不会为那些。

回答by Minhas Kamal

getMax() Function Without Any Logical Operation-

没有任何逻辑操作的 getMax() 函数-

int getMax(int a, int b){
    return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2;
}

---

---

Explanation:

解释：

Lets smash the 'max' into pieces,

让我们把“最大”粉碎成碎片，

max
= ( max + max ) / 2
= ( max + (min+differenceOfMaxMin) ) / 2
= ( max + min + differenceOfMaxMin ) / 2
= ( max + min + | max - min | ) ) / 2

So the function should look like this-

所以函数应该是这样的——

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2

Now,

现在，

absolute(x)
= x [if 'x' is positive] or -x [if 'x' is negative]
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )

In integer positive number the first bit (sign bit) is- 0; in negative it is- 1. By shifting bits to the right (>>) the first bit can be captured.

During right shift the empty space is filled by the sign bit. So 01110001 >> 2 = 00011100, while 10110001 >> 2 = 11101100.

As a result, for 8 bit number shifting 7 bit will either produce- 1 1 1 1 1 1 1 [0 or 1]for negative, or 0 0 0 0 0 0 0 [0 or 1]for positive.

Now, if ORoperation is performed with 00000001 (= 1), negative number yields- 11111111 (= -1), and positive- 00000001 (= 1).

在整数正数中，第一位（符号位）是- 0；负数是- 1。通过将位右移 (>>)，可以捕获第一位。

在右移期间，空白空间由符号位填充。所以01110001 >> 2 = 00011100，而10110001 >> 2 = 11101100。

因此，对于 8 位数字移位，7 位将产生 - 1 1 1 1 1 1 1 [0 或 1]表示负数，或0 0 0 0 0 0 0 [0 或 1]表示正数。

现在，如果使用00000001 (= 1)执行OR运算，则负数产生 - 11111111 (= -1)和正数 - 00000001 (= 1)。

So,

所以，

absolute(x)
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
= x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 )
= x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 )
= x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )

Finally,

最后，

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2

---

---

Another way-

另一种方式——

int getMax(int a, int b){
    int i[] = {a, b};
    return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ];
}