Warum wird solch komplexer Code zum Teilen einer vorzeichenbehafteten Ganzzahl mit einer Potenz von zwei ausgegeben?

Question

Wenn ich kompilieren diesen Code mit VC++ 10:

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

Ich erhalte diese Demontage:

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

, die eine Division durch eine Zweierpotenz mit einem logischen Recht sauber und präzise und ersetzt ist Verschiebung.

Doch wenn ich kompilieren diesen Code:

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

ich diese Demontage erhalten:

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 

, die einige Manipulationen durchführt, bevor sie eine richtige Stellenverschiebung tun.

Was sind die zusätzlichen Manipulationen? Warum reicht eine arithmetische Verschiebung nicht aus?

Answer 1

Der Grund ist, dass vorzeichenlose Division durch 2^n sehr einfach implementiert werden kann, während eine unterzeichnete Division etwas komplexer ist.

unsigned int u; 
int v; 

u/4096 entspricht u >> 12 für alle möglichen Werte von u.

v/4096 ist NICHT entspricht v >> 12 - es zusammenbricht, wenn v < 0, wie die Rundungsrichtung zum Verschieben gegenüber der Teilung unterschiedlich ist, als negative Zahlen beteiligt sind.

Answer 2

die "zusätzlichen Manipulationen" kompensieren die Tatsache, dass die arithmetische Rechtsverschiebung das Ergebnis in Richtung der negativen Unendlichkeit rundet, während die Division das Ergebnis in Richtung Null rundet.

Zum Beispiel ist -1 >> 1-1, während -1/20 ist.

Answer 3

Aus dem C-Standard:

Wenn ganzen Zahlen geteilt werden, ist das Ergebnis der/die Bediener algebraischen Quotienten mit jedem Bruchteil discarded.105) Wenn die Quotient a/b repräsentierbar ist, die Ausdruck (a/b) * b + a% b soll gleich a; Andernfalls ist das Verhalten von a/b und a% b undefiniert.

Es ist nicht schwer, an Beispiele zu denken, bei denen negative Werte für a dieser Regel bei reiner arithmetischer Verschiebung nicht folgen. Z.B.

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

die die Gleichung erfüllt, während

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

ist nicht mit Trunkierung Division und daher -2 * 4096 - 4095 ist sicherlich zu -8191 nicht gleich.

Beachten Sie, dass die Verschiebung von negativen Zahlen tatsächlich implementierungsdefiniert ist, daher hat der C-Ausdruck (-8191) >> 12 kein allgemein korrektes Ergebnis gemäß dem Standard.