c-使用位操作找到最小值

有人能向我解释下面的代码行吗。它用于查找两个数字中的最小值。

int min(int x, int y)
{
  return  y + ((x - y) & ((x - y) >>
            (sizeof(int) * CHAR_BIT - 1)));
}

提前谢谢。

它用于查找两个数字中的最小值。

不幸的是，该代码在int的许多组合中都失败了，使其价值非常低@harold一个好的编译器可以识别x < y ? x: y;并生成正确快速的代码@David C.Rankin

确定它是如何工作的并不像它是如何失败的那样有趣。

未定义的行为：如果x - y溢出，兼容的编译器可能会生成任何输出，甚至崩溃。优化编译器利用了这一点，让新程序员懊恼不已。
移位符号位是与some_negative_int >> (sizeof(int) * CHAR_BIT - 1)))一样的实现定义行为。int的算术右移是常见的，但没有由C.指定
如果int包含填充，则some_int >> (sizeof(int) * CHAR_BIT - 1)))可以超过允许的最大移位(这种情况很少见(。

OP的代码在x,y的许多组合中失败-121个测试用例中有31个失败-请参阅下文。"它通过算术移位来实现这一点"是实现定义的行为。x-y的潜在溢出是未定义的行为。如果不解决这些问题，任何答案都是不完整的。

角落案例"适用于任何其他尺寸"通常是正确的，但很少有平台会在int中使用填充，从而使sizeof(int) * CHAR_BIT - 1出现问题。

#include <stdio.h>
int minz(int x, int y) {
  return  y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}
void testmin(int x, int y) {
  static unsigned count = 0;
  static unsigned fail = 0;
  int min0 = x < y ? x: y;
  int min1 = minz(x,y);
  count++;
  if (min0 != min1) {
    fail++;
    printf("%u/%u min(%d, %d)--> %d, should be %dn", fail,count, x,y, min1, min0);
  }
}
int main(void) {
  const int i[]={INT_MIN, INT_MIN+1, INT_MIN+2, -2,-1,0, 1, 2, INT_MAX-2,INT_MAX-1, INT_MAX};
  int x,y;
  for (x=0; x<sizeof i/sizeof i[0]; x++) {
    for (y=0; y<sizeof i/sizeof i[0]; y++) {
      testmin(i[x],i[y]);
    }
  }
}

输出(故障(

1/7 min(-2147483648, 1)--> 1, should be -2147483648
2/8 min(-2147483648, 2)--> 2, should be -2147483648
3/9 min(-2147483648, 2147483645)--> 2147483645, should be -2147483648
4/10 min(-2147483648, 2147483646)--> 2147483646, should be -2147483648
5/11 min(-2147483648, 2147483647)--> 2147483647, should be -2147483648
6/19 min(-2147483647, 2)--> 2, should be -2147483647
7/20 min(-2147483647, 2147483645)--> 2147483645, should be -2147483647
8/21 min(-2147483647, 2147483646)--> 2147483646, should be -2147483647
9/22 min(-2147483647, 2147483647)--> 2147483647, should be -2147483647
10/31 min(-2147483646, 2147483645)--> 2147483645, should be -2147483646
11/32 min(-2147483646, 2147483646)--> 2147483646, should be -2147483646
12/33 min(-2147483646, 2147483647)--> 2147483647, should be -2147483646
13/44 min(-2, 2147483647)--> 2147483647, should be -2
14/56 min(0, -2147483648)--> 0, should be -2147483648
15/67 min(1, -2147483648)--> 1, should be -2147483648
16/68 min(1, -2147483647)--> 1, should be -2147483647
17/78 min(2, -2147483648)--> 2, should be -2147483648
18/79 min(2, -2147483647)--> 2, should be -2147483647
19/80 min(2, -2147483646)--> 2, should be -2147483646
20/89 min(2147483645, -2147483648)--> 2147483645, should be -2147483648
21/90 min(2147483645, -2147483647)--> 2147483645, should be -2147483647
22/91 min(2147483645, -2147483646)--> 2147483645, should be -2147483646
23/100 min(2147483646, -2147483648)--> 2147483646, should be -2147483648
24/101 min(2147483646, -2147483647)--> 2147483646, should be -2147483647
25/102 min(2147483646, -2147483646)--> 2147483646, should be -2147483646
26/103 min(2147483646, -2)--> 2147483646, should be -2
27/111 min(2147483647, -2147483648)--> 2147483647, should be -2147483648
28/112 min(2147483647, -2147483647)--> 2147483647, should be -2147483647
29/113 min(2147483647, -2147483646)--> 2147483647, should be -2147483646
30/114 min(2147483647, -2)--> 2147483647, should be -2
31/115 min(2147483647, -1)--> 2147483647, should be -1

如果为x<y，则此部分的值为-1，否则为0：

(x - y) >> (sizeof(int) * CHAR_BIT - 1)

它通过31位的算术移位(如果使用64位整数等，则为63位(来实现这一点。算术移位保留符号位，因此对于负值，您将得到所有位为1的结果，对于正值，您将获得所有位为0的结果。例如，如果x=2和y=4:

(2 - 4) >> (sizeof(int) * CHAR_BIT - 1)
== (-2) >> (4 * 8 -1)
== (-2) >> 31
== 0xFFFFFFFE >> 31
== 0xFFFFFFFF 
== -1

然后使用该值来屏蔽CCD_ 17。也就是说，如果是x<y，则得到(x - y) & -1 == (x - y)，否则得到(x - y) & 0 == 0。

最后，将该值与y相加，得到y + (x - y) == x或y + 0 == y。

(为了清楚起见，我们假设sizeof(int) == 4和CHAR_BIT == 8，但它适用于任何其他尺寸(

我们从最内部的表达式来解析它。

   (x - y) >> (sizeof(int) * CHAR_BIT - 1)
== (x - y) >> 31

int的>>通常是符号扩展右移(也称为算术右移(。移位31位只留下最上面的位，然后这个位被扩展到剩下的31位。这实际上相当于⌊(x-y(/2³¹⌋。

不难看出，每当x - y为负时，(x - y) >> 31就给出-1，反之则给出0。所以这实际上是一种写的奇特方法

   x - y < 0 ? -1 : 0
== x < y ? -1 : 0

请注意，这里我们说x - y < 0等效于x < y，但这仅在没有溢出的情况下有效例如，当x == 0和y == INT_MIN时，x - y将溢出到INT_MIN，这是负的，但x < y肯定是假的。

将其插入完整表达式：

   y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
== y + ((x - y) & (x < y ? -1 : 0))   // <- assume no overflow

当x < y时，我们得到(x - y) & -1。由于-1已经设置了所有比特，所以这相当于x - y。当x >= y时，我们得到(x - y) & 0，它是0。

因此，CCD_ 45只是一种写CCD_ 46的奇特方式。

== y + (x < y ? x - y : 0)
== x < y ? x : y

由于存在溢出错误，并且表达式非常棘手，因此在实践中永远不应该使用此表达式。只需使用(x < y) ? x : y。

相关内容

最新更新

热门标签：