使用位操作找到最小值

Question

任何人都可以向我解释以下代码行.它用于查找最少两个数字.

int min(int x, int y)

{

  return  y + ((x - y) & ((x - y) >>
            (sizeof(int) * CHAR_BIT - 1)));

}

提前致谢.

Answer 1

它用于查找最少两个数字.

不幸的是,这个代码很难用于int渲染非常低值的许多组合. @harold 一个好的编译器将识别x < y ? x: y;并生成正确和快速的代码.@David C. Rankin

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

1. 未定义的行为:应该x - y溢出,兼容的编译器可能会生成任何输出 - 甚至崩溃.优化编译器利用这一点使新程序员感到懊恼.

2. 移位符号位是实现定义的行为,如同 some_negative_int >> (sizeof(int) * CHAR_BIT - 1))).a的算术右移int是常见的,但未由C指定.

3. some_int >> (sizeof(int) * CHAR_BIT - 1)))可以超过允许的最大班次应该int包含填充(这是罕见的).

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 %d\n", 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