Dlaczego (a% 256) różni się od (a & 0xFF)?

Zawsze zakładałem, że robiąc (a % 256)optymalizator naturalnie użyje wydajnej operacji bitowej, tak jakbym pisał (a & 0xFF).

Podczas testowania w eksploratorze kompilatora gcc-6.2 (-O3):

// Type your code here, or load an example.
int mod(int num) {
    return num % 256;
}

mod(int):
    mov     edx, edi
    sar     edx, 31
    shr     edx, 24
    lea     eax, [rdi+rdx]
    movzx   eax, al
    sub     eax, edx
    ret

A kiedy próbujesz innego kodu:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Wygląda na to, że zupełnie czegoś mi brakuje. Jakieś pomysły?

To nie to samo. Spróbuj num = -79, a uzyskasz różne wyniki z obu operacji. (-79) % 256 = -79, podczas gdy (-79) & 0xffjest liczbą dodatnią.

Używając unsigned int, operacje są takie same, a kod prawdopodobnie będzie taki sam.

PS: Ktoś skomentował

Nie powinny być takie same, a % bokreśla się jako a - b * floor (a / b).

Nie tak to jest zdefiniowane w C, C ++, Objective-C (tj. We wszystkich językach, w których skompilowałby się kod w pytaniu).

Krótka odpowiedź

-1 % 256plony, -1a nie 255to, co jest -1 & 0xFF. Dlatego optymalizacja byłaby nieprawidłowa.

Długa odpowiedź

C ++ ma konwencję (a/b)*b + a%b == a, która wydaje się całkiem naturalna. a/bzawsze zwraca wynik arytmetyczny bez części ułamkowej (obcięcie do 0). W konsekwencji a%bma ten sam znak co alub wynosi 0.

Dzielenie -1/256daje 0i dlatego -1%256musi być -1, aby spełnić powyższy warunek ( (-1%256)*256 + -1%256 == -1). To oczywiście różni się od tego, -1&0xFFktóry jest 0xFF. Dlatego kompilator nie może zoptymalizować tak, jak chcesz.

Odpowiednia sekcja w standardzie C ++ [expr.mul §4] od N4606 mówi:

Dla argumentów całkowitych /operator daje iloraz algebraiczny z odrzuconą dowolną częścią ułamkową; jeśli iloraz a/bjest reprezentowalny w typie wyniku, (a/b)*b + a%bjest równy a[...].

Włączanie optymalizacji

Jednak przy użyciu unsignedtypów optymalizacja byłaby całkowicie poprawna , spełniając powyższą konwencję:

unsigned(-1)%256 == 0xFF

Zobacz także to .

Inne języki

Jest to obsługiwane bardzo różnie w różnych językach programowania, ponieważ można to sprawdzić w Wikipedii .

Od C ++ 11 num % 256musi być niedodatnia, jeśli numjest ujemna.

Tak więc wzorzec bitowy będzie zależał od implementacji typów ze znakiem w twoim systemie: dla ujemnego pierwszego argumentu wynikiem nie jest wyodrębnienie najmniej znaczących 8 bitów.

Byłoby inaczej, gdyby numw twoim przypadku było unsigned: w dzisiejszych czasach prawie oczekiwałbym, że kompilator wykona optymalizację, którą przytaczasz.

Nie mam telepatycznego wglądu w rozumowanie kompilatora, ale w takim przypadku %istnieje konieczność radzenia sobie z wartościami ujemnymi (i dzielenia zaokrągla do zera), podczas &gdy wynikiem jest zawsze niższe 8 bitów.

Te sardźwięki instrukcja do mnie jak „przesunięcie arytmetyczne prawo”, wypełnienie opuszczonego bitów o wartości bit znaku.

Mówiąc matematycznie, modulo definiuje się następująco:

a% b = a - b * floor (a / b)

To tutaj powinno ci wyjaśnić. Możemy wyeliminować podłogę dla liczb całkowitych, ponieważ dzielenie liczb całkowitych jest równoważne podłodze (a / b). Jeśli jednak kompilator miałby użyć ogólnej sztuczki, takiej jak sugerujesz, musiałby działać dla wszystkich a i wszystkich b. Niestety tak nie jest. Mówiąc matematycznie, twoja sztuczka jest w 100% poprawna dla liczb całkowitych bez znaku (widzę, że odpowiedź mówi, że liczby całkowite ze znakiem są łamane, ale mogę to potwierdzić ani zaprzeczyć, ponieważ -a% b powinno być dodatnie). Czy możesz jednak zrobić tę sztuczkę dla wszystkich b? Prawdopodobnie nie. Dlatego kompilator tego nie robi. W końcu, gdyby modulo można było łatwo zapisać jako jedną operację bitową, po prostu dodalibyśmy obwód modulo, taki jak dla dodawania i innych operacji.