Perché un codice così complesso viene emesso per dividere un numero intero con un potere di due?

Question

Quando compilo questo codice con VC++ 10:

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

ottengo questo smontaggio:

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

che è pulito e conciso e sostituito una divisione per una potenza di due, con un giusto logico cambio.

Eppure, quando ho compilare il codice:

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

ottengo questo lo smontaggio:

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 

che esegue alcune manipolazioni prima di fare uno spostamento aritmetico a destra.

Qual è la necessità di quelle manipolazioni extra? Perché uno spostamento aritmetico non è abbastanza?

Answer 1

La ragione è che la divisione non firmata di 2^n può essere implementata molto semplicemente, mentre la divisione firmata è un po 'più complessa.

unsigned int u; 
int v; 

u/4096 è equivalente a u >> 12 per tutti i possibili valori di u.

v/4096 è NON equivalente v >> 12 - si rompe quando v < 0, come la direzione di arrotondamento è differente per lo spostamento rispetto a divisione quando i numeri negativi sono coinvolti.

Answer 2

le "manipolazioni extra" compensano il fatto che il movimento a destra aritmetico arrotonda il risultato verso l'infinito negativo, mentre la divisione arrotonda il risultato verso zero.

Ad esempio, -1 >> 1 è -1, mentre -1/2 è 0.

Answer 3

Dalla standard C:

Quando interi vengono divisi, il risultato della/operatore è il quoziente algebrico con qualsiasi parte discarded.105 frazionaria) Se il quoziente a/b è rappresentabile, la espressione (a/b) * b + a% b deve essere uguale a a ; in caso contrario, il comportamento di a/b e a% b non è definito.

Non è difficile pensare a esempi in cui valori negativi per a non seguono questa regola con puro spostamento aritmetico. Per esempio.

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

che soddisfa l'equazione, mentre

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

non è divisione con troncamento, e quindi -2 * 4096 - 4095 non è certamente uguale a -8191.

Si noti che lo spostamento dei numeri negativi è in realtà definito dall'implementazione, quindi l'espressione C (-8191) >> 12 non ha un risultato generalmente corretto secondo lo standard.