解释这个片段,它可以在不使用if-else或其他比较运算符的情况下find两个整数的最大值?

find两个数字的最大值。 您不应该使用if-else或其他比较运算符。 我在网上公告板上发现这个问题,所以我想我应该问在StackOverflow

示例input:5,10输出:10

我发现这个解决scheme,有人可以帮我理解这些代码行

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

我们来剖析一下。 这第一行似乎是直截了当的 – 它存储了ab的区别。 如果a < b ,则此值为负,否则为非负。 这里实际上有一个错误 – 如果数字ab的差别太大,以至于无法放入一个整数,这会导致未定义的行为 – 哎呀! 那么让我们假设在这里不会发生。

在下一行,这是

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

这个想法是检查c的值是否为负数。 在几乎所有现代计算机中,数字都以称为二进制补码的格式存储,其中数字的最高位如果是正数则为0,如果数字为负则为1。 而且,大多数是32位。 (c >> 31)将数字向下移动31位,留下最低位数字的最高位。 下一步取这个数字并与1进行“与”运算(除了最后一位,其二进制表示为0)会擦除所有的高位,并给出最低位。 由于c >> 31的最低位是c >> 31的最高位,所以读取c的最高位为0或1.由于最高位为1,因此c为1,这是检查c是否为负的一种方式(1)或正(0)。 结合上述推理,如果a < b ,则k为1,否则为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 

这也是正确的最大值。

这里我们去: (a + b) / 2 + |a - b| / 2 (a + b) / 2 + |a - b| / 2

使用按位黑客

 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的“Twiddling Hacks”

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

这是基于与mike.dld的解决scheme相同的技术,但在这里我所做的并不那么“明显”。 一个“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

最简单的答案如下。

 #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); } 
 int max(int i, int j) { int m = ((ij) >> 31); return (m & j) + ((~m) & i); } 

这个解决scheme避免了乘法。 m将是0x00000000或0xffffffff

使用移动的想法来提取其他人张贴的标志,这是另一种方式:

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

这将两个数字按数组元素给出的最大数字推入一个数组中,其索引是两个数字之间的差值的符号位。

请注意:

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

以下是我想如何做这项工作。 它不像你想要的那么容易理解,但是当你从“如何做X而不使用显而易见的做X的方式开始”的时候,你必须期待这一点。理论上,这也放弃了一些可移植性, d必须find一个非常不寻常的系统来查看问题。

 #define BITS (CHAR_BIT * sizeof(int) - 1) int findmax(int a, int b) { int rets[] = {a, b}; return rets[unsigned(ab)>>BITS]; } 

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

以下是这些行正在做的事情:

c是ab。 如果c是负数,a <b。

k是c的第32位,它是c的符号位(假设是32位整数,如果在64位整数的平台上完成,这个代码将不起作用)。 它向右移动31位,移除最右边的31位,在最右边的位置留下符号位,然后用1移除所有左边的位(如果c为负值,将填充1)。 所以如果c是负数,k将是1,如果c是正数,则k是0。

那么max = a – k * c。 如果c是0,则意味着a> = b,所以max是一个 – 0 * c = a。 如果c是1,则意味着a <b,然后a-1 * c = a – (a-b)= a – a + b = b。

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

我还要补充一点,所有这些解决scheme都假设这两个数字都是整数。 如果他们是浮动,双打或更复杂的东西(BigInts,Rational数字等),那么你真的必须使用比较运算符。 一点技巧通常不会为那些做。

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

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

说明:

让我们把“最大”分成几块,

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

所以函数应该看起来像这样 –

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

现在,

 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] ) 

在整数正数中,第一位(符号位)是-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)执行运算,则负数产生-11111111 (= -1) ,正数00000001(= 1)

所以,

 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 ) 

最后,

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

static int mymax(int a,int b)

  { int[] arr; arr = new int[3]; arr[0] = b; arr[1] = a; arr[2] = a; return arr[Math.Sign(a - b) + 1]; } 

如果b> a那么(ab)将是负数,符号将返回-1,通过加1我们得到索引0是b,如果b = a那么ab将是0,+1将给出1索引,所以它并不重要如果我们返回a或b,当a> b时,ab将是正数,符号将返回1,加1,我们得到索引2,其中a存储。

 #include<stdio.h> main() { int num1,num2,diff; printf("Enter number 1 : "); scanf("%d",&num1); printf("Enter number 2 : "); scanf("%d",&num2); diff=num1-num2; num1=abs(diff); num2=num1+diff; if(num1==num2) printf("Both number are equal\n"); else if(num2==0) printf("Num2 > Num1\n"); else printf("Num1 > Num2\n"); } 

有两个技巧使用:整数表示技巧和math。

math把戏

对于给定的ab ,语句a < b意味着a - b < 0 。 让我们有一个单参数is_negative(x)的函数,如果参数为负,则返回1 ,否则返回零(请注意, is_negative(0) = 0 )。 那么函数max(a, b)可以定义为max(a, b) = a - is_negative(a - b)*(a - b)

certificate

有三种情况可能a < ba > ba = b

  • 如果a < b ,则a - b < 0 ,然后is_negative(a - b)1 。 因此, max = a - 1*(a - b) = b 。 所以,正如预期的那样。
  • 如果a > b ,则a - b > 0 ,并且is_negative(a - b)0 。 因此, max = a - 0*(a - b) = a 。 这是a
  • 如果a = b ,则a - b为零, is_negative(a - b)也为0 。 所以maxa

所以,对于所有情况下max作品如预期。

整数表示技巧

我们如何定义is_negative(x)而不使用分支? 现在的大多数现代架构都使用二进制补码algorithm。 所以,整数的第一位应该存储一个符号。 例如这里是-1表示:

 11111111111111111111111111111111 -> this is -1 ^ | +- This bit represents sign. 

基本上,如果一个整数是负数,则该位被设置,否则它是零。 对于32位整数x可以通过以下方式检索符号:

 (x >> 31) & 0x1; 

x >> 31 非循环位向右移动31位。 非循环意味着左侧的位为零,最后一位为已签名。 基本上-1变成1

 11111111111111111111111111111111 // before shift 00000000000000000000000000000001 // after shift 

(位移到右边,零填充到左边)

由于某些原因,代码片段的作者通过& 0x1双重清理0-31位。

有这个说法, is_negative(x) = (x >> 31) & 1

为什么这是错的

这里的弱点是整数运算。 整数算术是模块化的,所以它意味着MIN_INT - 1是零! 我们使用了一个假设a - b = 0意味着a = b ,而不是。 所以,algorithm在整数溢出的情况下被破坏。

我提供的代码是为了find两个数字之间的最大值,数字可以是任何数据types(整数,浮动)。 如果input数字相等,则函数返回数字。

 double findmax(double a, double b) { //find the difference of the two numbers double diff=ab; double temp_diff=diff; int int_diff=temp_diff; /* For the floating point numbers the difference contains decimal values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need to get a non-zero number on the left side of '.' */ while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) ) { temp_diff = temp_diff * 10; int_diff = temp_diff; } /* shift the sign bit of variable 'int_diff' to the LSB position and find if it is 1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of the two numbers (variable 'diff') then subtract it with the variable a. */ return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 )); } 

描述

  • 函数的第一件事情是将参数作为double并且返回types为double。 这样做的原因是要创build一个function,可以find所有types的最大值。 当提供整数types数字,或者一个是整数,另一个是浮点数时,也由于隐式转换,函数也可以用来查找整数的最大值。
  • 基本的逻辑很简单,假设我们有两个数字a&b,如果ab> 0(即差异是正的),那么a是最大的else if ab == 0,那么两者是相等的,如果ab <0(即差异是 – ve)b是最大的。
  • 符号位被保存为内存中的最高位(MSB)。 如果MSB是1,反之亦然。 要检查MSB是1还是0,我们将MSB移到LSB位置,按位与&1,如果结果是1,那么数字是-ve else no。 是+ ve。 这个结果是通过声明获得的:

    int_diff >>(sizeof(int)* 8 – 1)&1

这里要从MSB到LSB的符号位,我们右移它到k-1位(其中k是存储器中所需的位数,取决于系统的types)。 这里k = sizeof(int)* 8作为sizeof()给出了保存一个整数所需要的字节数来得到no。 我们将它乘以8.在右移之后,我们应用按位与&来得到结果。

  • 现在得到结果(让我们假设为r)为1(对于-ve diff)和0(对于+ ve diff),我们将结果与两个数的差值相乘,逻辑如下给出:

    1. 如果a> b,那么ab> 0,也就是+ ve,所以结果是0(即r = 0)。 所以a-(ab)* r => a-(ab)* 0,它给出了'a'作为最大值。
    2. 如果a <b,那么ab <0即是-ve,所以结果是1(即r = 1)。 所以a-(ab)* r => a-(ab)* 1 => a-a + b => b,给出'b'作为最大值。
  • 现在有两个剩余的点1.使用while循环和2.为什么我已经使用variables“int_diff”作为一个整数。 为了正确回答这些问题,我们必须理解一些观点:

    1. 浮点型值不能用作位运算符的操作数。
    2. 由于上述原因,我们需要通过使用按位运算符来获取整数值中的值以获得差异的符号。 这两点描述了整型variables'int_diff'的需要。
    3. 现在假设我们发现variables'差异'的差异,现在'差异'的值有三种可能性,而不pipe这些值的符号如何。 (一个)。 (b)。 0 <| diff | <1,(c)。 | DIFF | == 0。
    4. 当我们将一个double值赋给整型variables时,小数部分会丢失。
    5. 对于(a)'int_diff'> 0(即1,2,…)的值。 对于其他两种情况int_diff = 0。
    6. 条件(temp_diff-int_diff)|| 0.0检查是否diff == 0,所以两个数字相等。
    7. 如果diff!= 0,那么我们检查int_diff | 0是否为真,即情况(b)为真
    8. 在while循环中,我们尝试将int_diff的值设置为非零值,这样int_diff的值也会得到diff的符号。

这里有几个比特旋转方法来获得两个整数值的最大值:

方法1

 int max1(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return (a & ~mask) | (b & mask); } 

说明:

  • (a – b)>> SIGN_BIT_SHIFT – 如果a > ba - b为正,因此符号位为0 ,掩码为0x00.00 。 否则, a < b如此a - b为负数,符号位为1 ,移位后我们得到一个0xFF..FF的掩码
  • (a& 0xFF..FF ) – 如果掩码是0xFF..FF ,那么0xFF..FF0x00..00然后这个值是0 。 否则, ~mask0xFF..FF ,值是a
  • (b&mask) – 如果mask是0xFF..FF ,那么这个值是b 。 否则, mask0x00..00 ,值是0

最后:

  • 如果a >= ba - b是正数,我们得到max = a | 0 = a max = a | 0 = a
  • 如果a < ba - b是负数,我们得到max = 0 | b = b max = 0 | b = b

方法2

 int max2(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return a ^ ((a ^ b) & mask); } 

说明:

  • 面具说明与方法1相同。 如果a > b掩码是0x00..00 ,否则掩码是0xFF..FF
  • 如果掩码是0x00..00 ,那么(a ^ b) & mask0x00..00
  • 如果掩码是0xFF..FF ,那么(a ^ b) & maska ^ b

最后:

  • 如果a >= b ,我们得到a ^ 0x00..00 = a
  • 如果a < b ,我们得到a ^ a ^ b = b

问题中所描述的逻辑可以解释为:如果第一个数字小于0,则将减去第一个数字,否则将从第一个数字减去差值以获得第二个数字。 我发现了另一个math解决scheme,我认为这个概念有点简单。

考虑到a和b作为给定的数字

 c=|a/b|+1; d=(c-1)/b; smallest number= a - d*(ab); 

同样,这个想法是find0或1的k,然后用两个数的差值相乘,最后从第一个数中减去这个数,得到两个数中较小的一个。 如果第二个数字为零,PS解决scheme将失败

 int a=151; int b=121; int k=Math.abs(ab); int j= a+b; double k1=(double)(k); double j1= (double) (j); double c=Math.ceil(k1/2) + Math.floor(j1/2); int c1= (int) (c); System.out.println(" Max value = " + c1); 

(a / b)* b +(b / a)* a – (a / b)*(b / a)* a +(abs(a-b)%a)%b

有一个方法

  public static int Min(int a, int b) { int dif = (int)(((uint)(a - b)) >> 31); return a * dif + b * (1 - dif); } 

和一个

 return (a>=b)?b:a; 

猜猜我们可以乘以他们的位数比较,例如:

 int max=(a>b)*a+(a<=b)*b;