Dlaczego preferujemy dopełnienie dwójki zamiast znaku i wielkości dla liczb podpisanych?

Wikipedia mówi wszystko:

Układ dwóch dopełniaczy ma tę zaletę, że nie wymaga, aby obwody dodawania i odejmowania badały znaki operandów w celu określenia, czy dodać, czy odjąć. Ta właściwość sprawia, że system jest zarówno prostszy do wdrożenia, jak i zdolny do łatwej obsługi arytmetyki o wyższej precyzji. Ponadto zero ma tylko jedną reprezentację, eliminując subtelności związane z ujemnym zerem, które istnieją w dopełniaczu ones'- systemy.

Innymi słowy, dodawanie jest takie samo, wether lub nie liczba jest ujemna.

Mimo , że to pytanie jest stare, pozwól mi umieścić moje 2 centy.

Zanim to wyjaśnię, wróćmy do podstaw. Dopełniacz 2 ' to dopełniacz 1 + 1 . Teraz, co jest dopełnieniem 1 i jakie jest jego znaczenie w dodatku.

Suma dowolnej liczby n-bitowej i jej dopełnienia 1 daje najwyższą możliwą liczbę, która może być reprezentowana przez te N-bity. Przykład:

 0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
 1111  (the highest number that we can represent by 4 bits)

Teraz co się stanie, jeśli spróbujemy dodać 1 więcej do wyniku. Spowoduje to przepełnienie.

Wynikiem będzie 1 0000, czyli 0 ( ponieważ pracujemy z liczbami 4-bitowymi, (1 po lewej jest przepełnieniem)

Więc,

Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)

Ktoś wtedy zdecydował się nazwać dopełnienie 1 + 1 jako dopełnienie 2. Tak więc powyższe stwierdzenie staje się: Dowolna liczba n ' bita + jej dopełniacz 2 = 0 co oznacza dopełnienie 2 liczby = - (tej liczby)

To wszystko rodzi jeszcze jedno pytanie , dlaczego możemy użyć tylko (n-1) N bitów do reprezentowania liczby dodatniej i dlaczego po lewej n-ty bit reprezentuje znak (0 po lewej oznacza +liczba ve, a 1 oznacza - liczba ve). np. dlaczego używamy tylko pierwszych 31 bitów int w Javie do reprezentowania liczby dodatniej, jeśli 32-gi bit to 1, jego Liczba a-ve.

 1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________

1 0000 (wynik jest zerowy, z przepełnieniem 1)

Tak więc system (n + 2 ' N) = 0, nadal działa. Jedyną niejednoznacznością jest tutaj dopełnienie 2 z 12 to 0100, które niejednoznacznie reprezentuje również +8, inne niż reprezentujące -12 w systemie dopełniacza 2s.

Ten problem zostanie rozwiązany, jeśli liczby dodatnie zawsze będą miały 0 w lewym bitie. W takim przypadku dopełniacz ich 2 zawsze będzie miał 1 w lewym największym bitie i nie będziemy mieli dwuznaczności tego samego zbioru bitów reprezentujących liczbę dopełniacza 2, jak również liczbę + ve.

Dopełniacz Two pozwala na dodawanie i odejmowanie w normalny sposób (tak jak dla liczb niepodpisanych). Zapobiega również -0 (oddzielny sposób reprezentowania 0, który nie byłby równy 0 przy normalnej metodzie porównywania liczb bit po bitu).

Ma to na celu uproszczenie sum i różnic liczbowych. suma liczb ujemnych i dodatnich skodyfikowanych w dopełnieniach 2 jest taka sama jak sumowanie ich w sposób normalny.

Zwyczajową implementacją operacji jest "flip the bits and add 1", ale istnieje inny sposób jej zdefiniowania, który prawdopodobnie wyjaśnia uzasadnienie. Dopełniacz 2 jest formą, którą otrzymujesz, jeśli przyjmiesz zwykłą niepodpisaną reprezentację, w której każdy bit kontroluje następną potęgę 2 i po prostu uczynisz najważniejszy termin ujemnym.

Pobranie 8-bitowej wartości a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀

The usual unsigned binary interpretation is:
2⁷*a₇ + 2⁶*a₆ + 2⁵*a₅ + 2⁴*a₄ + 2³*a₃ + 2²*a₂ + 2¹*a₁ + 2⁰*a₀
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255

Interpretacja dopełniacza obu jest następująca:
-2⁷*a₇ + 2⁶*a₆ + 2⁵*a₅ + 2⁴*a₄ + 2³*a₃ + 2²*a₂ + 2¹*a₁ + 2⁰*a₀
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1

Żaden z pozostałych bitów w ogóle nie zmienia znaczenia, a przenoszenie do₇ jest "przepełnienie" i nie oczekuje się, aby działać, więc prawie wszystkie operacje arytmetyczne działają bez modyfikacji(jak inni zauważyli). Wielkość znaku zazwyczaj sprawdza bit znaku i używa różnych logika.

Dopełniacz dwójki pozwala na dodawanie liczb ujemnych i dodatnich bez żadnej specjalnej logiki.

Jeśli próbowałeś dodać 1 i -1 używając swojej metody
10000001 (-1)
+00000001 (1)
dostajesz
10000010 (-2)

Zamiast tego, używając dopełniacza two, możemy dodać

11111111 (-1)
+00000001 (1) dostajesz
00000000 (0)

To samo dotyczy odejmowania.

Również, jeśli spróbujesz odjąć 4 od 6 (dwie liczby dodatnie) Możesz 2 ' s complement 4 i dodać dwa Razem 6 + (-4) = 6 - 4 = 2

Oznacza to, że odejmowanie i dodawanie zarówno liczb dodatnich, jak i ujemnych może być wykonane przez ten sam układ w procesorze.

Do rozwinięcia na innych odpowiedzi:

W dopełniaczu dwójkowym

• Dodawanie jest tym samym mechanizmem, co dodawanie zwykłych dodatnich liczb całkowitych.
• odejmowanie też się nie zmienia
• mnożenie też!

Podział wymaga innego mechanizmu.

Wszystko to jest prawdą, ponieważ dopełnienie dwójki jest zwykłą arytmetyką modularną, gdzie wybieramy, że niektóre liczby są ujemne przez odjęcie modulo.

[[26]}czytając odpowiedzi na to pytanie, natknąłem się na ten komentarz [edycja].

Dopełniacz 2 z 0100 (4) będzie równy 1100. Teraz 1100 to 12, jeśli powiem normalnie. Więc, Kiedy mówię normalny 1100 to jest 12, ale kiedy mówię 2 dopełnienie 1100 to -4? Również w Javie gdy 1100 (Załóżmy na razie 4 bity) jest zapisane wtedy w jaki sposób określa się, czy jest to +12 czy -4 ?? - hagrawal 2 lipca o 16: 53

Moim zdaniem pytanie zadane w tym komentarzu jest dość ciekawe i dlatego chciałbym najpierw to przeformułować, a następnie podać odpowiedź i przykład.

Pytanie-w jaki sposób system może ustalić, jak należy interpretować jeden lub więcej sąsiadujących bajtów? W szczególności, w jaki sposób system może ustalić, czy dany ciąg bajtów jest zwykłą liczbą binarną czy liczbą dopełniającą 2?

Odpowiedź-system określa, jak interpretować sekwencję bajtów poprzez typy. Typy definiują

• ile bajtów musi be considered
• jak te bajty muszą być interpretowane

Przykład - poniżej Zakładamy, że

• char's mają długość 1 bajtu
• short's mają długość 2 bajtów
• int ' s I float's mają długość 4 bajtów

Proszę pamiętać, że te rozmiary są specyficzne dla mojego systemu. Chociaż są dość powszechne, mogą się różnić w zależności od systemu. Jeśli jesteś ciekaw, jakie są one w Twoim systemie, użyj operatora sizeof .

Pierwszy z wszystkich definiujemy tablicę zawierającą 4 bajty i inicjalizujemy wszystkie z nich do liczby binarnej 10111101, odpowiadającej liczbie szesnastkowej BD.

// BD(hexadecimal) = 10111101 (binary)
unsigned char   l_Just4Bytes[ 4 ]   =   { 0xBD, 0xBD, 0xBD, 0xBD };

Następnie odczytujemy zawartość tablicy używając różnych typów.

unsigned char i signed char

// 10111101 as a PLAIN BINARY number equals 189
printf( "l_Just4Bytes as unsigned char  -> %hi\n", *( ( unsigned char* )l_Just4Bytes ) );

// 10111101 as a 2'S COMPLEMENT number equals -67
printf( "l_Just4Bytes as signed char    -> %i\n", *( ( signed char* )l_Just4Bytes ) );

unsigned short i short

// 1011110110111101 as a PLAIN BINARY number equals 48573
printf( "l_Just4Bytes as unsigned short -> %hu\n", *( ( unsigned short* )l_Just4Bytes ) );

// 1011110110111101 as a 2'S COMPLEMENT number equals -16963
printf( "l_Just4Bytes as short          -> %hi\n", *( ( short* )l_Just4Bytes ) );

unsigned int, int oraz float

// 10111101101111011011110110111101 as a PLAIN BINARY number equals 3183328701
printf( "l_Just4Bytes as unsigned int   -> %u\n", *( ( unsigned int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a 2'S COMPLEMENT number equals -1111638595
printf( "l_Just4Bytes as int            -> %i\n", *( ( int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a IEEE 754 SINGLE-PRECISION number equals -0.092647
printf( "l_Just4Bytes as float          -> %f\n", *( ( float* )l_Just4Bytes ) );

4 bajty pamięci RAM (l_Just4Bytes[ 0..3 ]) pozostają zawsze takie same. Zmienia się tylko to, jak je interpretujemy.

Znowu, mówimy systemowi jak interpretować je poprzeztypy .

Na przykład, powyżej użyliśmy następujących typów do interpretacji zawartości tablicyl_Just4Bytes

• unsigned char: 1 bajt w prostym binarnym
• signed char: 1 bajt w dopełniaczu 2
• unsigned short: 2 bajty w zwykłej notacji binarnej
• short: 2 bajty w dopełniaczu 2
• unsigned int: 4 bajty w zwykłej notacji binarnej
• int: 4 bajty w 2 ' S dopełniacz
• float: 4 bajty w notacji pojedynczej precyzji IEEE 754

Profesor Jerry Cain ze Stanford wyjaśnia dopełnienie tych dwóch rzeczy, w drugim wykładzie (wyjaśnienie dotyczące dopełnienia dwójki zaczyna się około godziny 13: 00) z serii wykładów o nazwie paradygmaty programowania dostępnych na kanale Standforda na YouTube. Oto link do serii wykładów: http://www.youtube.com/view_play_list?p=9D558D49CA734A02 .

Dopełniacz Two jest używany, ponieważ jest prostszy do implementacji w obwodach, a także nie pozwala na ujemne zero.

Jeśli istnieją bity x, dopełniacz two będzie się wahał od +(2^x/2+1) do- (2^x/2). Dopełnienie będzie przebiegać od +(2^x/2) do- (2^x/2), ale pozwoli na ujemne zero (0000 jest równe 1000 W 4-bitowym systemie dopełnienia 1).

Cóż, twoim zamiarem nie jest odwrócenie wszystkich bitów Twojej liczby binarnej. W rzeczywistości odejmuje się każdą jego cyfrę od 1. To po prostu szczęśliwy zbieg okoliczności, że odejmowanie 1 od 1 skutkuje 0, a odejmowanie 0 od 1 skutkuje 1. Więc przerzucanie bitów skutecznie przeprowadza to odejmowanie.

Ale dlaczego znajdujesz różnicę każdej cyfry od 1? Nie jesteś. Twoim rzeczywistym zamiarem jest obliczenie różnicy danej liczby binarnej od innej liczby binarnej, która ma tę samą liczbę cyfr, ale zawiera tylko 1. na przykład, jeśli twoja liczba to 10110001, po odwróceniu wszystkich tych bitów, skutecznie obliczasz (11111111 - 10110001).

To wyjaśnia pierwszy krok w obliczeniu dopełniacza dwójki. Teraz dołączmy drugi krok-dodanie 1 - również na zdjęciu.

Dodaj 1 do powyższego równania binarnego:

11111111 - 10110001 + 1

Co dostajesz? To:

100000000 - 10110001

To jest końcowe równanie. I wykonując te dwa kroki starasz się znaleźć tę, ostateczną różnicę: numer binarny odejmowany od innej liczby binarnej z jedną dodatkową cyfrą i zawierający zera z wyjątkiem najbardziej znaczącej pozycji bitowej.

Ale dlaczego tak naprawdę tęsknimy za tą różnicą? Cóż, od tej chwili, myślę, że byłoby lepiej, gdybyś przeczytał artykuł Wikipedii.

Wykonujemy tylko operację dodawania zarówno dla dodawania, jak i odejmowania. Dodajemy drugi operand do pierwszego operandu w celu dodania. Dla odejmowania dodajemy dopełnienie 2 drugiego operandu do pierwszego operandu.

Z reprezentacją dopełniacza 2 nie potrzebujemy oddzielnych komponentów cyfrowych do odejmowania-używane są tylko dopełniacze i dopełniacze.

Warto zauważyć, że na niektórych wczesnych maszynach dodawania, przed dniami komputerów cyfrowych, odejmowanie byłoby wykonywane przez operatora wprowadzającego wartości za pomocą innego kolorowego zestawu legend na każdym klawiszu (więc każdy klawisz wprowadzałby dziewięć minus liczba do odjęcia), a naciśnięcie specjalnego przycisku zakładałoby przeniesienie do obliczeń. Tak więc, na maszynie sześciocyfrowej, aby odjąć 1234 od wartości, operator naciskałby klawisze, które normalnie wskazywałyby "998,765" i naciśnij przycisk, aby dodać tę wartość plus jeden do obliczeń w toku. Arytmetyka dopełniacza dwójki jest po prostu binarnym odpowiednikiem wcześniejszej arytmetyki dopełniacza dziesięciu.

Zaletą wykonywania odejmowania metodą dopełniacza jest redukcja sprzętu
złożoność.Nie ma potrzeby stosowania innego obwodu cyfrowego do dodawania i odejmowania.obie dodawanie i odejmowanie są wykonywane tylko przez dodawarkę.

Główną zaletą reprezentacji dopełniacza dwójki, która nie została jeszcze tutaj wymieniona, jest to, że dolne bity sumy dopełniacza dwójki, różnicy lub iloczynu zależą tylko od odpowiednich bitów operandów. Powodem, dla którego 8-bitowa wartość podpisana dla -1 wynosi 11111111 jest to, że odjęcie dowolnej liczby całkowitej, której najniższe 8 bitów to 00000001 od dowolnej innej liczby całkowitej, której najniższe 8 bitów to 0000000 da liczbę całkowitą, której najniższe 8 bitów to 11111111. Matematycznie, wartość -1 będzie nieskończonym ciągiem 1, ale wszystkie wartości w zakresie określonego typu integer będą albo wszystkie 1, albo wszystkie 0 poza określonym punktem, więc jest to wygodne dla komputerów, aby "podpisać-rozszerzyć" najbardziej znaczący bit liczby, tak jakby reprezentował nieskończoną liczbę 1 lub 0.

Dopełniacz dwójkowy jest jedyną reprezentacją liczby podpisanej, która działa dobrze, gdy mamy do czynienia z typami większymi niż naturalny rozmiar słowa maszyny binarnej, od kiedy wykonując dodawanie lub odejmowanie, kod może pobrać najniższy fragment każdego operanda, obliczyć najniższy fragment wyniku i zapisać go, a następnie załadować następny fragment każdego operanda, obliczyć następny fragment wyniku i zapisać go itp. Tak więc, nawet procesor, który wymaga wszystkich dodatków i odejmowań, aby przejść przez pojedynczy rejestr 8-bitowy, może obsłużyć 32-bitowe sygnowane liczby rozsądnie efektywnie (wolniej niż w przypadku rejestru 32-bitowego, oczywiście, ale nadal wykonalny).

Podczas stosowania ze wszystkich innych podpisanych reprezentacji dozwolonych przez Standard C, każdy bit wyniku może być potencjalnie dotknięty dowolnym bitem operandów, co sprawia, że konieczne jest albo trzymanie całej wartości w rejestrach naraz, albo wykonywanie obliczeń z dodatkowym krokiem, który w przynajmniej niektórych przypadkach wymagałby odczytu, modyfikacji i przepisania każdego fragmentu wyniku.

Istnieją różne typy reprezentacji to:

1. niepodpisana reprezentacja liczb
2. podpisana reprezentacja liczb
3. reprezentacja dopełniacza
4. reprezentacja dopełniacza dwójki

- Niepodpisana reprezentacja liczb używana do reprezentowania tylko liczb dodatnich

- podpisana reprezentacja liczb używana do reprezentowania zarówno liczby dodatniej, jak i ujemnej. W reprezentacji Signed number bit MSB reprezentuje bit sign oraz bit rest reprezentuje liczbę. Gdy MSB jest 0 oznacza liczbę jest dodatnia, a gdy MSB jest 1 oznacza liczbę jest ujemna.

Problem z podpisaną reprezentacją liczb polega na tym, że istnieją dwie wartości dla 0.

Problem z reprezentacją dopełniacza polega na tym, że istnieją dwie wartości dla 0.

Ale jeśli użyjemy reprezentacji dopełniacza dwójki to będzie tylko jedna wartość dla 0 dlatego reprezentujemy liczby ujemne w dopełniaczu dwójki forma.

Source: Why negative numbers are stored in two ' S complementary form bytesofgigabajts

Jedna satysfakcjonująca odpowiedź na pytanie, dlaczego dopełniacz Two2 jest używany do reprezentowania liczb ujemnych, a nie układu dopełniacza jest taka, że System dopełniacza dwójki rozwiązuje problem wielokrotnych reprezentacji 0 i potrzeby end-around-carry, które istnieją w systemie dopełniacza Jedynki reprezentującej liczby ujemne.

Aby uzyskać więcej informacji odwiedź https://en.wikipedia.org/wiki/Signed_number_representations

Dla End-around-carry Visit https://en.wikipedia.org/wiki/End-around_carry