解释这个片段,它在不使用if-else或任何其他比较运算符的情况下找到最多两个整数？

Question

找到最多两个数字.您不应该使用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;  
}

Answer 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进行AND运算(除了最后一位之外,其二进制表示为0)的下一步将擦除所有较高位,并为您提供最低位.由于最低位c >> 31是最高位c,因此将最高位读取c为0或1.由于最高位为1 iff c为1,因此这是检查c是负(1)还是正(0)的方法.将这种推理与上述相结合,k如果a < b是则为1 ,否则为0.

最后一步是这样做:

int max = a - k * c;

如果a < b,那么k == 1和k * 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

这也是正确的最大值.

Answer 2

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

Answer 3

使用按位黑客攻击

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

如果你知道INT_MIN <= x - y <= INT_MAX,那么你可以使用以下,这更快,因为(x - y)只需要评估一次.

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

资料来源:肖恩·埃伦·安德森(Sean Eron Anderson

Answer 4

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

这是基于与mike.dld解决方案相同的技术,但在这里我不太"明显"."abs"操作看起来像是在比较某些东西的符号,但我在这里利用了sqrt()将始终返回正平方根的事实,所以我正在平方(ab)将其全部写出来然后正方形 - 再次生根,添加+ b并除以2.

您将看到它始终有效:例如,用户的10和5示例得到sqrt(100 + 25 - 100)= 5然后加10和5得到20除以2得到10.

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

Answer 5

最简单的答案如下.

#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);
}

Answer 6

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

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