Czy ((a + (b & 255)) & 255) to to samo co ((a + b) & 255)?

Przeglądałem kod w C ++ i znalazłem coś takiego:

(a + (b & 255)) & 255

Podwójny AND mnie zirytował, więc pomyślałem:

(a + b) & 255

( ai bsą 32-bitowymi liczbami całkowitymi bez znaku)

Szybko napisałem skrypt testowy (JS), aby potwierdzić moją teorię:

for (var i = 0; i < 100; i++) {
    var a = Math.ceil(Math.random() * 0xFFFF),
        b = Math.ceil(Math.random() * 0xFFFF);

    var expr1 = (a + (b & 255)) & 255,
        expr2 = (a + b) & 255;

    if (expr1 != expr2) {
        console.log("Numbers " + a + " and " + b + " mismatch!");
        break;
    }
}

Chociaż skrypt potwierdził moją hipotezę (obie operacje są sobie równe), nadal mu nie ufam, ponieważ 1) losowy i 2) nie jestem matematykiem, nie mam pojęcia, co robię .

Przepraszam też za tytuł Lisp-y. Zapraszam do edycji.

Oni są tacy sami. Oto dowód:

Najpierw zwróć uwagę na tożsamość (A + B) mod C = (A mod C + B mod C) mod C

Powtórzmy problem, traktując go a & 255jako zastępcę a % 256. To prawda, ponieważ ajest bez znaku.

Tak (a + (b & 255)) & 255jest(a + (b % 256)) % 256

To jest to samo, co (a % 256 + b % 256 % 256) % 256(zastosowałem powyższą tożsamość: zauważ, że modi %są one równoważne dla typów bez znaku).

Upraszcza to, do (a % 256 + b % 256) % 256czego się staje (a + b) % 256(ponowne zastosowanie tożsamości). Następnie możesz przywrócić operator bitowy z powrotem, aby dać

(a + b) & 255

uzupełnienie dowodu.

W dodawaniu pozycyjnym, odejmowaniu i mnożeniu liczb bez znaku w celu uzyskania wyników bez znaku, bardziej znaczące cyfry danych wejściowych nie wpływają na mniej znaczące cyfry wyniku. Dotyczy to zarówno arytmetyki binarnej, jak i arytmetyki dziesiętnej. Odnosi się to również do arytmetyki ze znakiem „uzupełnienie do dwóch”, ale nie do arytmetyki ze znakiem - wielkość.

Jednak musimy być ostrożni przy pobieraniu reguł z arytmetyki binarnej i stosowaniu ich w C (wierzę, że C ++ ma takie same zasady jak C w tym zakresie, ale nie jestem w 100% pewien), ponieważ arytmetyka C ma pewne tajemne reguły, które mogą nas zepsuć w górę. Arytmetyka bez znaku w C jest zgodna z prostymi binarnymi regułami zawijania, ale przepełnienie arytmetyczne ze znakiem jest niezdefiniowanym zachowaniem. Gorzej w pewnych okolicznościach C automatycznie „promuje” niepodpisany typ na (podpisany) int.

Niezdefiniowane zachowanie w C może być szczególnie podstępne. Głupi kompilator (lub kompilator na niskim poziomie optymalizacji) prawdopodobnie zrobi to, czego oczekujesz na podstawie twojego zrozumienia arytmetyki binarnej, podczas gdy kompilator optymalizujący może złamać twój kod w dziwny sposób.

Wracając do wzoru w pytaniu, równoważność zależy od typów operandów.

Jeśli są to liczby całkowite bez znaku, których rozmiar jest większy lub równy rozmiarowi, intwówczas zachowanie operatora dodawania przy przepełnieniu jest dobrze zdefiniowane jako proste binarne zawijanie. To, czy maskujemy wysokie 24 bity jednego operandu przed operacją dodawania, nie ma wpływu na młodsze bity wyniku.

Jeśli są to liczby całkowite bez znaku, których rozmiar jest mniejszy niż int, zostaną podwyższone do (ze znakiem) int. Przepełnienie liczb całkowitych ze znakiem jest niezdefiniowanym zachowaniem, ale przynajmniej na każdej platformie, z którą się spotkałem, różnica w rozmiarze między różnymi typami liczb całkowitych jest na tyle duża, że ​​pojedyncze dodanie dwóch promowanych wartości nie spowoduje przepełnienia. Więc znowu możemy wrócić do prostego binarnego argumentu arytmetycznego, aby uznać instrukcje za równoważne.

Jeśli są to liczby całkowite ze znakiem, których rozmiar jest mniejszy niż int, to znowu nie może dojść do przepełnienia, a w implementacjach z dopełnieniem dwójkowym możemy polegać na standardowym binarnym argumencie arytmetycznym, aby powiedzieć, że są równoważne. W przypadku implementacji typu znak-wielkość lub jedynek nie byłyby równoważne.

OTOH, jeśli ai bbyłyby liczbami całkowitymi ze znakiem, których rozmiar byłby większy lub równy rozmiarowi int, to nawet w implementacjach uzupełnień do dwóch zdarzają się przypadki, w których jedna instrukcja byłaby dobrze zdefiniowana, a druga byłaby niezdefiniowanym zachowaniem.

Lemat: a & 255 == a % 256bez znaku a.

Unsigned amoże być zapisane jako m * 0x100 + bczęść unsigned m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Z obu definicji wynika, że a & 255 == b == a % 256.

Dodatkowo potrzebujemy:

• własność rozdzielcza: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• definicja dodawania bez znaku, matematycznie: (a + b) ==> (a + b) % (2 ^ 32)

A zatem:

(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255      // def'n of addition
                      = ((a + (b % 256)) % (2^32)) % 256      // lemma
                      = (a + (b % 256)) % 256                 // because 256 divides (2^32)
                      = ((a % 256) + (b % 256 % 256)) % 256   // Distributive
                      = ((a % 256) + (b % 256)) % 256         // a mod n mod n = a mod n
                      = (a + b) % 256                         // Distributive again
                      = (a + b) & 255                         // lemma

Więc tak, to prawda. Dla 32-bitowych liczb całkowitych bez znaku.

A co z innymi typami liczb całkowitych?

• W przypadku 64-bitowych liczb całkowitych bez znaku wszystkie powyższe mają zastosowanie, po prostu podstawiając 2^64za 2^32.
• W przypadku 8- i 16-bitowych liczb całkowitych bez znaku dodawanie obejmuje promocję do int. Z intpewnością nie spowoduje to przepełnienia ani ujemnego wyniku w żadnej z tych operacji, więc wszystkie pozostają ważne.
• Dla podpisane liczb całkowitych, jeśli jedna a+blub a+(b&255)przepełnienia, to niezdefiniowane zachowanie. Tak więc równość nie może się utrzymać - są przypadki, w których (a+b)&255zachowanie jest nieokreślone, ale (a+(b&255))&255nie jest.

Tak, (a + b) & 255jest w porządku.

Pamiętasz dodatek w szkole? Dodajesz liczby cyfra po cyfrze i dodajesz wartość przeniesienia do następnej kolumny cyfr. Nie ma sposobu, aby późniejsza (bardziej znacząca) kolumna cyfr wpłynęła na już przetworzoną kolumnę. Z tego powodu nie ma znaczenia, czy wyzerujesz cyfry tylko w wyniku, czy też najpierw w argumencie.

Powyższe nie zawsze jest prawdą, standard C ++ pozwala na implementację, która by to zepsuła.

Taka Deathstation 9000 : - ) musiałaby używać 33-bitowego int, gdyby OP oznaczało unsigned short„32-bitowe liczby całkowite bez znaku”. Gdyby unsigned intchodziło o to, DS9K musiałby używać 32-bitowego inti 32-bitowego unsigned intz bitem wypełnienia. (Liczby całkowite bez znaku muszą mieć taki sam rozmiar jak ich odpowiedniki ze znakiem, zgodnie z §3.9.1 / 3, a bity wypełniające są dozwolone w §3.9.1 / 1). Inne kombinacje rozmiarów i bitów wypełniających również będą działać.

O ile wiem, jest to jedyny sposób, aby go złamać, ponieważ:

• Reprezentacja liczb całkowitych musi używać „czysto binarnego” schematu kodowania (§ 3.9.1 / 7 i przypis), wszystkie bity z wyjątkiem bitów wypełniających i bitu znaku muszą mieć wartość 2 ⁿ
• Promocja int jest dozwolona tylko wtedy, gdy intmoże reprezentować wszystkie wartości typu źródłowego (§ 4.5 / 1), więc intmusi mieć co najmniej 32 bity składające się na wartość plus bit znaku.
• intnie może mieć wartości większej liczby bitów (nie licząc bitu znaku), niż 32, ponieważ inny dodatek nie może przelać.

Masz już sprytną odpowiedź: arytmetyka bez znaku to arytmetyka modulo i dlatego wyniki będą się utrzymywać, możesz to udowodnić matematycznie ...

Jednak jedną fajną rzeczą dotyczącą komputerów jest to, że są szybkie. Rzeczywiście, są tak szybkie, że wyliczenie wszystkich poprawnych kombinacji 32 bitów jest możliwe w rozsądnym czasie (nie próbuj z 64 bitami).

Tak więc w twoim przypadku osobiście lubię po prostu rzucić to w komputer; mniej czasu zajmuje mi przekonanie samego siebie, że program jest poprawny, niż przekonanie samego siebie, niż dowód matematyczny jest poprawny i że nie przeoczyłem szczegółów w specyfikacji ¹ :

#include <iostream>
#include <limits>

int main() {
    std::uint64_t const MAX = std::uint64_t(1) << 32;
    for (std::uint64_t i = 0; i < MAX; ++i) {
        for (std::uint64_t j = 0; j < MAX; ++j) {
            std::uint32_t const a = static_cast<std::uint32_t>(i);
            std::uint32_t const b = static_cast<std::uint32_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

To wylicza wszystkie możliwe wartości a i bw przestrzeni 32-bitów i sprawdza, czy równość, czy nie. Jeśli tak się nie stanie, drukuje przypadek, który nie zadziałał, co można wykorzystać jako kontrolę poczytalności.

I, zgodnie z Clang : równość .

Ponadto, biorąc pod uwagę, że reguły arytmetyczne są niezależne od szerokości bitów (powyżej int niezależne od szerokości bitów szerokości bitowej), ta równość będzie obowiązywać dla dowolnego typu liczby całkowitej bez znaku o 32 bitach lub więcej, w tym 64 bitach i 128 bitach.

Uwaga: w jaki sposób kompilator może wyliczyć wszystkie wzorce 64-bitowe w rozsądnych ramach czasowych? Nie może. Pętle zostały zoptymalizowane. W przeciwnym razie wszyscy zginęlibyśmy przed zakończeniem egzekucji.

Początkowo udowodniłem to tylko dla 16-bitowych liczb całkowitych bez znaku; niestety C ++ to szalony język, w którym małe liczby całkowite (mniejsze niż int) są najpierw konwertowane naint .

#include <iostream>

int main() {
    unsigned const MAX = 65536;
    for (unsigned i = 0; i < MAX; ++i) {
        for (unsigned j = 0; j < MAX; ++j) {
            std::uint16_t const a = static_cast<std::uint16_t>(i);
            std::uint16_t const b = static_cast<std::uint16_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: "
                      << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

I jeszcze raz, według Clanga : Równość obowiązuje .

Cóż, proszę bardzo :)

¹ Oczywiście, gdyby program kiedykolwiek przypadkowo wyzwolił niezdefiniowane zachowanie, niewiele by to udowodniło.

Szybka odpowiedź brzmi: oba wyrażenia są równoważne

• ponieważ ai bsą 32-bitowymi liczbami całkowitymi bez znaku, wynik jest taki sam nawet w przypadku przepełnienia. arytmetyka bez znaku gwarantuje to: wynik, który nie może być reprezentowany przez wynikowy typ liczby całkowitej bez znaku, jest redukowany modulo liczba o jeden większa niż największa wartość, która może być reprezentowana przez wynikowy typ.

Długa odpowiedź brzmi: nie ma znanych platform, na których te wyrażenia by się różniły, ale Standard tego nie gwarantuje, ze względu na zasady integralnej promocji.

• Jeśli typ aand b(32-bitowe liczby całkowite bez znaku) ma wyższą rangę niż int, obliczenia są wykonywane jako bez znaku, modulo 2 ³² i dają ten sam zdefiniowany wynik dla obu wyrażeń dla wszystkich wartości ai b.

• I odwrotnie, jeśli typ ai bjest mniejszy niż int, oba są podwyższane do, inta obliczenia są wykonywane przy użyciu arytmetyki ze znakiem, w której przepełnienie wywołuje niezdefiniowane zachowanie.

  • Jeśli intma co najmniej 33 bity wartości, żadne z powyższych wyrażeń nie może się przepełnić, więc wynik jest doskonale zdefiniowany i ma taką samą wartość dla obu wyrażeń.

  • Jeśli intma dokładnie 32 bity wartości, obliczenia mogą spowodować przepełnienie dla obu wyrażeń, na przykład wartości a=0xFFFFFFFFi b=1spowodować przepełnienie w obu wyrażeniach. Aby tego uniknąć, musiałbyś pisać ((a & 255) + (b & 255)) & 255.

• Dobra wiadomość jest taka, że ​​nie ma takich platform ¹ .

¹ Dokładniej, nie istnieje taka rzeczywista platforma, ale można skonfigurować DS9K tak, aby wykazywał takie zachowanie i nadal był zgodny ze standardem C.

Identyczne przy założeniu braku przepełnienia . Żadna z wersji nie jest naprawdę odporna na przepełnienie, ale wersja double i wersja jest na nie bardziej odporna. Nie znam systemu, w którym przepełnienie w tym przypadku jest problemem, ale widzę, jak autor robi to w przypadku, gdy taki istnieje.

Tak, możesz to udowodnić za pomocą arytmetyki, ale istnieje bardziej intuicyjna odpowiedź.

Przy dodawaniu każdy bit wpływa tylko na te bardziej znaczące niż on sam; nigdy te mniej znaczące.

Dlatego cokolwiek zrobisz z wyższymi bitami przed dodaniem, nie zmieni wyniku, o ile zachowasz tylko bity mniej istotne niż zmodyfikowany najniższy bit.

Dowód jest trywialny i pozostawiony czytelnikowi jako ćwiczenie

Ale aby faktycznie uzasadnić to jako odpowiedź, pierwsza linia kodu mówi, że weź ostatnie 8 bitów b** (wszystkie wyższe bity bustawione na zero) i dodaj to doa a następnie weź tylko ostatnie 8 bitów wyniku, ustawiając wszystkie wyższe bity do zera.

Druga linia mówi dodaj aib weź ostatnie 8 bitów z wszystkimi wyższymi bitami równymi zero.

W wyniku tylko ostatnich 8 bitów ma znaczenie. Dlatego tylko ostatnie 8 bitów jest znaczących w danych wejściowych.

** ostatnie 8 bitów = 8 LSB

Warto również zauważyć, że dane wyjściowe byłyby równoważne

char a = something;
char b = something;
return (unsigned int)(a + b);

Jak powyżej, tylko 8 LSB jest znaczących, ale wynik jest unsigned intrówny zero ze wszystkimi innymi bitami. a + bWyleje, tworząc oczekiwany rezultat.