¿Por qué se emite este código complejo para dividir un entero con signo por una potencia de dos?

Question

Cuando compilar este código con VC++ 10:

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

consigo este desmontaje:

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

que está limpio y conciso y sustituye una división por potencias de dos, con un derecho lógica cambio.

Sin embargo, cuando puedo compilar este código:

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

consigo este desmontaje:

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 

que realiza algunas manipulaciones antes de realizar un desplazamiento aritmético a la derecha.

¿Cuál es la necesidad de esas manipulaciones adicionales? ¿Por qué un cambio aritmético no es suficiente?

Answer 1

La razón es que la división sin signo por 2^n se puede implementar de manera muy simple, mientras que la división con signo es algo más compleja.

unsigned int u; 
int v; 

u/4096 es equivalente a u >> 12 para todos los valores posibles de u.

v/4096 es NO equivalente a v >> 12 - se descompone cuando v < 0, como la dirección de redondeo es diferente para el cambio de frente división cuando los números negativos están involucrados.

Answer 2

las "manipulaciones adicionales" compensan el hecho de que el desplazamiento aritmético hacia la derecha redondea el resultado hacia el infinito negativo, mientras que la división redondea el resultado hacia cero.

Por ejemplo, -1 >> 1 es -1, mientras que -1/2 es 0.

Answer 3

de la norma C:

Cuando enteros se dividen, el resultado de la/operador es el cociente algebraico con cualquier parte discarded.105 fraccional) Si el cociente a/b es representable, la expresión (a/b) * b + a% b será igual a; de lo contrario, el comportamiento de a/by a% b no está definido.

No es difícil pensar en ejemplos donde los valores negativos para a no siguen esta regla con el cambio aritmético puro. P.ej.

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

que satisface la ecuación, mientras que

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

no es la división con truncamiento, y por lo tanto -2 * 4096 - 4095 sin duda no es igual a -8,191.

Tenga en cuenta que el desplazamiento de números negativos en realidad está definido por la implementación, por lo que la expresión C (-8191) >> 12 no tiene un resultado generalmente correcto según el estándar.