Dlaczego taki złożony kod jest emitowany do dzielenia liczby całkowitej ze znakiem przez potęgę dwóch?

Question

Kiedy mogę skompilować ten kod z VC++ 10:

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

otrzymuję ten demontaż:

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

który jest czysty i zwięzły i zastąpione przez podział mocy dwa z logicznym prawo przesunięcie.

Jednak kiedy mogę skompilować ten kod:

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

otrzymuję ten demontaż:

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 

który wykonuje pewne manipulacje przed wykonaniem właściwej arytmetyczne przesunięcie.

Jakie są dodatkowe manipulacje? Dlaczego przesunięcie arytmetyczne nie jest wystarczające?

Answer 1

Powodem jest to, że niepodpisany podział przez 2^n może być zaimplementowany w bardzo prosty sposób, podczas gdy podział na znaki jest nieco bardziej złożony.

unsigned int u; 
int v; 

u/4096 odpowiada u >> 12 dla wszystkich możliwych wartości u.

v/4096 jest NIE równoważne v >> 12 - rozkłada się gdy jest v < 0, jako kierunek zaokrąglania różni się dla przesunięcia w stosunku podziału, gdy zaangażowane są liczby ujemne.

Answer 2

"Dodatkowe manipulacje" rekompensują fakt, że arytmetyczna przesunięcie w prawo zaokrągla wynik w kierunku ujemnej nieskończoności, natomiast dzielenie zaokrągla wynik w kierunku zera.

Na przykład -1 >> 1 to -1, natomiast -1/2 to 0.

Answer 3

od standardu C:

Gdy całkowite są podzielone wynikiem/użytkownika jest algebraiczna iloraz z każdej części ułamkowej discarded.105) jeżeli iloraz a/b jest zakodowania The wyrażenie (a/b) * b + a% b oznacza równe a; w przeciwnym razie zachowanie zarówno a/b, jak i% b jest niezdefiniowane.

Nie jest trudno wymyślić przykłady, w których wartości ujemne nie są zgodne z tą zasadą z czystym przesunięciem arytmetycznym. Na przykład.

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

która spełnia równanie, natomiast

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

jest podział o skróconym i dlatego -2 * 4096 - 4095 jest z pewnością nie jest równa -8191.

Należy zauważyć, że przesunięcie liczb ujemnych jest faktycznie definiowane przez implementację, więc wyrażenie C (-8191) >> 12 nie ma ogólnie poprawnego wyniku zgodnie ze standardem.