44

このコードをVC++10でコンパイルすると、次のようになります。

DWORD ran = rand();
return ran / 4096;

私はこの分解を取得します：

299: {
300:    DWORD ran = rand();
  00403940  call        dword ptr [__imp__rand (4050C0h)]  
301:    return ran / 4096;
  00403946  shr         eax,0Ch  
302: }
  00403949  ret

これはクリーンで簡潔であり、論理的な右シフトで除算を2の累乗に置き換えました。

しかし、私がこのコードをコンパイルすると、次のようになります。

int ran = rand();
return ran / 4096;

私はこの分解を取得します：

299: {
300:    int ran = rand();
  00403940  call        dword ptr [__imp__rand (4050C0h)]  
301:    return ran / 4096;
  00403946  cdq  
  00403947  and         edx,0FFFh  
  0040394D  add         eax,edx  
  0040394F  sar         eax,0Ch  
302: }
  00403952  ret

右算術シフトを実行する前に、いくつかの操作を実行します。

それらの余分な操作の必要性は何ですか？算術シフトでは不十分なのはなぜですか？

4

3 に答える 3

91

その理由は、2 ^ nによる符号なし除算は非常に簡単に実装できるのに対し、符号付き除算はやや複雑だからです。

unsigned int u;
int v;

u / 4096u >> 12のすべての可能な値と同等ですu。

v / 4096と同等ではありません-負の数が含まれる場合、シフトと除算では丸め方向が異なるため、がのv >> 12場合に分解されます。v < 0

于 2012-10-02T14:21:34.180 に答える
34

「余分な操作」は、算術右シフトが結果を負の無限大に丸めるのに対し、除算は結果をゼロに丸めるという事実を補償します。

たとえば、-1 >> 1is ですが-1、-1/2is です0。

于 2012-10-02T14:23:12.193 に答える
10

C標準から：

105) 商 a/b が表現可能である場合、式 (a/b)*b + a%b は a に等しくなります。それ以外の場合、a/b と a%b の両方の動作は未定義です。

a の負の値が純粋な算術シフトでこの規則に従わない例を考えるのは難しくありません。例えば

(-8191) / 4096 -> -1
(-8191) % 4096 -> -4095

これは方程式を満たしますが、

(-8191) >> 12 -> -2 (assuming arithmetic shifting)

は切り捨てによる除算ではないため、-2 * 4096 - 4095-8191 と等しくないことはほぼ確実です。

負の数のシフトは実際には実装定義であるため、C 式(-8191) >> 12は標準に従って一般的に正しい結果を持たないことに注意してください。

于 2012-10-02T14:30:22.950 に答える