logo标签列表

C位运算谜题

cbitoperation
5
/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/4),
 *   including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */

int ezThreeFourths(int x) {
   int z = x+x+x;
   int sign_z = z>>31;
   return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);
}

我尝试解决这个难题，但是

错误：测试ezThreeFourths（-2147483648 [0x80000000]）失败...
...给出-536870911 [0xe0000001]。 应该是-536870912 [0xe0000000]

使用gcc（GCC）4.1.2 20080704（Red Hat 4.1.2-51）编译

这个解决方案有什么问题？

1
嗯...我在我的电脑上运行了这段代码的测试，我必须说它似乎对于你在这里给出的测试用例和示例都能正常工作。甚至对于2147483647，我也得到了正确的结果。 - Lefteris
你使用的编译器是哪个？ - Remy Lebeau
2
你把它分解了以查看所有中间值了吗？ - EboMike
我忘了提到我用哪个编译器运行测试。 它是在Windows下使用的GCC 4.4.1。 - Lefteris
使用gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-51)编译 - user1114371
4个回答
2

以下是我的做法：

#include <stdio.h>
#include <limits.h>

int ThreeFourths(int x)
{
  int x3 = x + x + x;
  return (x3 >= 0) ? (x3 >> 2) : -(int)((UINT_MAX - x3 + 1) >> 2);
}

int testData[] =
{
   0,
   1,
  -1,
   2,
  -2,
   3,
  -3,
   4,
  -4,
   5,
  -5,
  -9,
  11,
  INT_MAX / 2 + 1,
  INT_MIN
};

int main(void)
{
  int i;

  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
  {
    printf("      %d * 3 / 4 = %d\n",
           testData[i], testData[i] * 3 / 4);
    printf("ThreeFourths(%d) = %d\n",
           testData[i], ThreeFourths(testData[i]));
  }
  return 0;
}

输出：

      0 * 3 / 4 = 0
ThreeFourths(0) = 0
      1 * 3 / 4 = 0
ThreeFourths(1) = 0
      -1 * 3 / 4 = 0
ThreeFourths(-1) = 0
      2 * 3 / 4 = 1
ThreeFourths(2) = 1
      -2 * 3 / 4 = -1
ThreeFourths(-2) = -1
      3 * 3 / 4 = 2
ThreeFourths(3) = 2
      -3 * 3 / 4 = -2
ThreeFourths(-3) = -2
      4 * 3 / 4 = 3
ThreeFourths(4) = 3
      -4 * 3 / 4 = -3
ThreeFourths(-4) = -3
      5 * 3 / 4 = 3
ThreeFourths(5) = 3
      -5 * 3 / 4 = -3
ThreeFourths(-5) = -3
      -9 * 3 / 4 = -6
ThreeFourths(-9) = -6
      11 * 3 / 4 = 8
ThreeFourths(11) = 8
      1073741824 * 3 / 4 = -268435456
ThreeFourths(1073741824) = -268435456
      -2147483648 * 3 / 4 = -536870912
ThreeFourths(-2147483648) = -536870912

我没有在负整数上使用右移的原因很简单。这些移位的结果是实现定义的（根据 C 标准），不能保证与我们期望的带符号扩展的右移相同，因为它是最常见的实现。
我写的是 (UINT_MAX - x3 + 1) 而不是简单的 -x3，因为它可能会导致有符号溢出（当 x3 = INT_MIN 时，它是一个负的2的幂），这是未定义的行为（再次根据 C 标准）。即使已知这种未定义行为是无害的，简单的否定仍然可能无法产生正数（因为有符号整数的2的补码表示中存在不对称性）。 x + x + x 仍然可能产生有符号溢出，就像 x * 3 一样。因此，这是相同的未定义行为。
顺便说一下，由于有符号溢出会导致未定义行为，因此甚至不应该要求您实现它们，更不用说在 UB 发生时具有特定的结果期望了。
1
int ezThreeFourths(int x) {  


  int z = x+x+x;  
  int sign_z = z>>31;  


  return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);  

}

适用于非负数。此外，您不应该对您编写的 "代码"撒谎。考虑到确切的代码是在"2008-01-26"编写的。

0

我使用Embarcadero C++ 6.43没有问题：

// x = 2147483647
int ezThreeFourths(int x)
{
    int z = x+x+x;
    // z = 2147483645 (6442450941[0x17FFFFFFD] truncated to 32-bits!)

    int sign_z = z>>31;
    // sign_z = (2147483645 >> 31) = 0

    return ((z>>2)&(~sign_z)) + (((z>>2)+1)&sign_z);
    // = ((2147483645 >> 2) & (~0)) + (((2147483645 >> 2) + 1) & 0)
    // = (536870911 & 0xFFFFFFFF) + ((536870911+1) & 0)
    // = (536870911 & 0xFFFFFFFF) + (536870912 & 0)
    // = (536870911 & 0xFFFFFFFF) + 0
    // = (536870911 & 0xFFFFFFFF)
    // = 536870911
}
0

你的处理负数向零舍入的方法在输入值能被4整除的情况下无法正确工作。0x80000000就是一个这样的例子，但如果你尝试使用一个小值，问题可能更容易看出来。

例如：ezThreeFourths(-8) = -5 [ 应该是 -6 ]

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接