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 標準に従って) であり、最も一般的な実装であるため、予想される符号拡張付きの右シフトと同じであるとは限りません。

代わりに、符号付きオーバーフローが発生する可能性があるため ( =が 2 の負の累乗である場合)、未定義の動作をする可能性があるため (C 標準に従って)、(UINT_MAX - x3 + 1)代わりに書きました。また、この未定義の動作が無害であることがわかっている場合でも、単純な否定では正の数を生成できない可能性があります (符号付き整数の 2 の補数表現の非対称性のため)。-x3x3INT_MIN

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

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 に答える
0

入力値が 4 で均等に除算される場合、負の数をゼロに丸めるというアプローチは正しく機能しません。

例: ezThreeFourths(-8) = -5 [ -6 である必要があります]

于 2012-02-08T05:58:05.927 に答える