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) 编译

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

4

4 回答 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，因此甚至不应该在法律上要求您实现它们，更不用说对 UB 发生时的结果有具体的期望了。

于 2012-02-08T08:03:39.140 回答
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”中

于 2012-02-08T13:29:06.437 回答
0

在输入值除以 4 的情况下，您将负数四舍五入的方法无法正常工作。0x80000000 就是这样一个示例，但如果您尝试使用较小的值，可能更容易看到问题。

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

于 2012-02-08T05:58:05.927 回答
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
}
于 2012-02-08T03:05:39.310 回答