Dlaczego dla liczb podpisanych wolę uzupełnienie do dwóch od znaku i wielkości?

Jestem ciekawy, czy istnieje powód, dla którego do reprezentowania -1 w formacie binarnym używane jest uzupełnienie dwóch: odwracanie bitów i dodawanie 1?

-1 jest reprezentowane przez 11111111 (uzupełnienie dwóch) zamiast (według mnie bardziej intuicyjnego) 10000001, który jest binarny 1 z pierwszym bitem jako flagą ujemną.

Oświadczenie: Nie polegam na arytmetyce binarnej w mojej pracy!

Dokonano tego, aby dodawanie nie wymagało żadnej specjalnej logiki do obsługi liczb ujemnych. Sprawdź artykuł na Wikipedii .

Powiedzmy, że masz dwie liczby, 2 i -1. W twoim „intuicyjnym” sposobie przedstawiania liczb byłyby odpowiednio 0010i 1001(trzymam się 4 bitów dla rozmiaru). W uzupełnieniu tych dwóch są 0010i 1111. Powiedzmy, że chcę je dodać.

Uzupełnienie dwóch jest bardzo proste. Dodajesz liczby normalnie, a każdy bit przeniesienia na końcu jest odrzucany. Są więc dodawane w następujący sposób:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 wynosi 1, co jest oczekiwanym wynikiem „2 + (- 1)”.

Jednak w metodzie „intuicyjnej” dodawanie jest bardziej skomplikowane:

  0010
+ 1001
= 1011

Który to -3, prawda? Proste dodanie nie działa w tym przypadku. Należy zauważyć, że jedna z liczb jest ujemna i w takim przypadku użyj innego algorytmu.

W przypadku tej „intuicyjnej” metody przechowywania odejmowanie jest inną operacją niż dodawanie, wymagającą dodatkowych kontroli liczb przed ich dodaniem. Ponieważ chcesz, aby najbardziej podstawowe operacje (dodawanie, odejmowanie itp.) Przebiegały jak najszybciej, musisz przechowywać liczby w sposób umożliwiający korzystanie z najprostszych możliwych algorytmów.

Dodatkowo w „intuicyjnej” metodzie przechowywania istnieją dwa zera:

0000  "zero"
1000  "negative zero"

Które są intuicyjnie takie same, ale mają dwie różne wartości, gdy są przechowywane. Każda aplikacja będzie musiała podjąć dodatkowe kroki, aby upewnić się, że niezerowe wartości również nie są ujemne.

Jest jeszcze jeden bonus do przechowywania int w ten sposób, i wtedy trzeba zwiększyć szerokość rejestru, w którym jest przechowywana wartość. W przypadku uzupełnienia dwóch, przechowywanie 4-bitowej liczby w 8-bitowym rejestrze jest kwestią powtórzenia Najbardziej znaczący bit:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1110 (negative two, in four bits)
11111110 (negative two, in eight bits)

Wystarczy spojrzeć na znak mniejszego słowa i powtarzać go, aż wypełni się szerokość większego słowa.

Swoją metodą musisz wyczyścić istniejący bit, co jest dodatkową operacją oprócz wypełniania:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1010 (negative two, in four bits)
10000010 (negative two, in eight bits)

Nadal musisz ustawić te dodatkowe 4 bity w obu przypadkach, ale w przypadku „intuicyjnym” musisz również wyczyścić 5. bit. To jeden mały krok w jednej z najbardziej podstawowych i powszechnych operacji obecnych w każdej aplikacji.

Wikipedia mówi wszystko:

Zaletą układu dwóch uzupełnień jest to, że nie wymaga, aby obwód dodawania i odejmowania sprawdzał znaki operandów w celu ustalenia, czy dodać, czy odjąć. Ta właściwość sprawia, że ​​system jest zarówno prostszy we wdrożeniu, jak i może z łatwością obsługiwać arytmetykę o wyższej precyzji. Również zero ma tylko jedną reprezentację, co eliminuje subtelności związane z ujemnym zerem, które istnieje w systemach z ich dopełnieniem.

Innymi słowy, dodawanie jest takie samo, niezależnie od tego, czy liczba jest ujemna.

Chociaż to pytanie jest stare, pozwólcie, że dodam 2 centy.

Zanim to wyjaśnię, wróćmy do podstaw. Uzupełnienie 2 'jest uzupełnieniem 1' + 1. Teraz, co stanowi uzupełnienie 1 i jakie jest jego znaczenie.

Suma dowolnej liczby n-bitowej i jej uzupełnienia 1 daje najwyższą możliwą liczbę, którą mogą reprezentować 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)

Co się stanie, jeśli spróbujemy dodać jeszcze 1 do wyniku. Spowoduje to przepełnienie.

Wynik będzie wynosił 1 00000 (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 postanowił nazwać uzupełnienie 1 + 1 jako uzupełnienie 2'. Tak więc powyższa instrukcja staje się następująca: Dowolna liczba n-bitowa + jej uzupełnienie 2 = 0, co oznacza uzupełnienie 2 liczby = - (tej liczby)

Wszystko to daje jeszcze jedno pytanie, dlaczego możemy użyć tylko (n-1) n bitów do przedstawienia liczby dodatniej i dlaczego lewy najbardziej n-ty bit reprezentuje znak (0 na skrajnym lewym bicie oznacza liczbę + ve, a 1 oznacza -ve number). np. dlaczego używamy tylko pierwszych 31 bitów int w java do reprezentowania liczby dodatniej, jeśli 32 bit to 1, to jest liczba -ve.

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

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

Tak więc system (n + 2'komplet n) = 0 nadal działa. Jedyną niejednoznacznością jest tutaj dopełnienie 2 dla 12 to 0100, które dwuznacznie reprezentuje również +8, poza reprezentowaniem -12 w układzie dopełniacza 2s.

Ten problem zostanie rozwiązany, jeśli liczby dodatnie zawsze mają 0 w lewym bicie. W takim przypadku ich uzupełnienie 2 zawsze będzie miało 1 w lewym bicie, i nie będziemy mieli dwuznaczności tego samego zestawu bitów reprezentujących liczbę uzupełnień 2, a także liczbę + ve.

Uzupełnienie do dwóch umożliwia dodawanie i odejmowanie w normalny sposób (tak jak w przypadku liczb niepodpisanych). Zapobiega także -0 (oddzielny sposób reprezentowania 0, który nie byłby równy 0 przy normalnej metodzie porównywania liczb krok po kroku).

ma to na celu uproszczenie sum i różnic liczbowych. suma liczby ujemnej i liczby dodatniej skodyfikowanych w uzupełnieniach 2 jest tym samym, co sumowanie ich w normalny sposób.

Zwykłą implementacją operacji jest „odwracanie bitów i dodawanie 1”, ale istnieje inny sposób jej zdefiniowania, który prawdopodobnie sprawia, że ​​uzasadnienie jest jaśniejsze. Uzupełnienie 2 jest formą, którą otrzymujesz, jeśli weźmiesz zwykłą niepodpisaną reprezentację, w której każdy bit kontroluje następną potęgę 2, i po prostu czyni najbardziej znaczący termin ujemnym.

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

Zwykła interpretacja binarna bez znaku to:
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 tych dwóch:
-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 przeniesienie na ₇ jest „przepełnieniem” i nie powinno działać, więc prawie wszystkie operacje arytmetyczne działają bez modyfikacji (jak zauważyli inni). Wielkość znaku generalnie sprawdza bit znaku i używa innej logiki.

Uzupełnienie dwóch pozwala na dodawanie liczb ujemnych i dodatnich bez specjalnej logiki.

Jeśli próbujesz dodać 1 i -1 za pomocą metody
10000001 (-1)
+00000001 (1)
, otrzymasz
10000010 (-2)

Zamiast tego, stosując uzupełnienie do dwóch, możemy dodać

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

To samo dotyczy odejmowania.

Ponadto, jeśli spróbujesz odjąć 4 od 6 (dwie liczby dodatnie), możesz uzupełnić 2 do 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 obwód w jednostce centralnej.

Aby rozwinąć inne odpowiedzi:

W uzupełnieniu do dwóch

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

Podział wymaga innego mechanizmu.

Wszystko to jest prawdą, ponieważ uzupełnienie dwóch jest po prostu normalną arytmetyką modułową, w której wybieramy niektóre liczby jako ujemne, odejmując moduł.

Czytając odpowiedzi na to pytanie, natknąłem się na ten komentarz [zredagowany].

Uzupełnienie 2 do 0100 (4) wyniesie 1100. Teraz 1100 to 12, jeśli mówię normalnie. Tak więc, kiedy mówię normalny 1100, to jest to 12, ale kiedy mówię, że 1100 uzupełnienia 2 to wtedy -4? Także w Javie, gdy 1100 (na razie załóżmy 4 bity), to jak to ustalić, czy jest to +12 czy -4 ?? - hagrawal 2 lipca o 16:53

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

PYTANIE - Jak system może ustalić, w jaki sposób 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 dana sekwencja bajtów jest zwykłą liczbą binarną, czy liczbą uzupełniającą 2?

ODPOWIEDŹ - System ustala sposób interpretacji sekwencji bajtów według typów. Typy definiują

• ile bajtów należy wziąć pod uwagę
• jak należy interpretować te bajty

PRZYKŁAD - poniżej zakładamy, że

• charmają 1 bajt długości
• shortmają 2 bajty długości
• inti floatmają długość 4 bajtów

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

Przede wszystkim definiujemy tablicę zawierającą 4 bajty i inicjalizujemy je wszystkie na liczbę binarną 10111101, odpowiadającą liczbie szesnastkowej BD.

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

Następnie odczytujemy zawartość tablicy za pomocą 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, intafloat

// 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 w RAM ( l_Just4Bytes[ 0..3 ]) zawsze pozostają dokładnie takie same. Jedyne, co się zmienia, to sposób ich interpretacji.

Ponownie mówimy systemowi, jak interpretować je według typów .

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

• unsigned char: 1 bajt w formacie binarnym
• signed char: 1 bajt w uzupełnieniu do 2
• unsigned short: 2 bajty w zwykłym zapisie binarnym
• short: 2 bajty w uzupełnieniu do 2
• unsigned int: 4 bajty w zwykłym zapisie binarnym
• int: 4 bajty w uzupełnieniu do 2
• float: 4 bajty w notacji pojedynczej precyzji IEEE 754

[EDYCJA] Ten post został edytowany po komentarzu użytkownika4581301. Dziękujemy za poświęcenie czasu na upuszczenie tych kilku pomocnych linii!

Możesz oglądać profesora Jerry'ego Caina ze Stanforda wyjaśniającego uzupełnienie obu, w drugim wykładzie (wyjaśnienie dotyczące uzupełnienia 2 rozpoczyna się około 13:00) w serii wykładów zatytułowanych „Paradygmaty programowania”, które można obejrzeć na kanale YouTube w Standford. Oto link do serii wykładów: http://www.youtube.com/view_play_list?p=9D558D49CA734A02 .

Stosowane jest uzupełnienie do dwóch, ponieważ jest łatwiejsze do wdrożenia w obwodach, a także nie pozwala na ujemne zero.

Jeśli jest x bitów, uzupełnienie dwóch będzie się wahać od + (2 ^ x / 2 + 1) do - (2 ^ x / 2). Uzupełnienie będzie działało od + (2 ^ x / 2) do - (2 ^ x / 2), ale pozwoli na ujemne zero (0000 jest równe 1000 w systemie uzupełnień 4-bitowych 1).

Cóż, twoim celem nie jest tak naprawdę odwrócenie wszystkich bitów twojej liczby binarnej. Właściwie to odejmuje każdą cyfrę od 1. To tylko szczęśliwy zbieg okoliczności, że odejmowanie 1 od 1 powoduje 0 i odejmowanie 0 od 1 daje 1. Tak więc przerzucanie bitów skutecznie wykonuje to odejmowanie.

Ale dlaczego znajdujesz różnicę dla każdej cyfry od 1? Cóż, nie jesteś. Rzeczywistym celem jest obliczenie różnicy podanej liczby binarnej od innej liczby binarnej, która ma taką samą liczbę cyfr, ale zawiera tylko 1. Na przykład, jeśli Twój numer to 10110001, po odwróceniu wszystkich tych bitów efektywnie obliczasz (11111111 - 10110001).

To wyjaśnia pierwszy krok w obliczeniach uzupełnienia Two. 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, próbujesz znaleźć tę ostatnią różnicę: liczba binarna odjęta od innej liczby binarnej z jedną dodatkową cyfrą i zawierająca zera, z wyjątkiem pozycji bitu najbardziej znaczącego.

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

Wykonujemy tylko operację dodawania dla dodawania i odejmowania. W celu dodania dodajemy drugi operand do pierwszego operandu. Aby odjąć, dodajemy dopełnienie 2 drugiego operandu do pierwszego operandu.

Dzięki reprezentacji dopełniacza 2 nie potrzebujemy oddzielnych komponentów cyfrowych do odejmowania - używane są tylko sumatory i dopełniacze.

Warto zauważyć, że na niektórych maszynach z wczesnym dodawaniem, przed dniami komputerów cyfrowych, odejmowanie odbywałoby się, gdy operator wprowadzałby wartości przy użyciu innego koloru zestawu legend na każdym klawiszu (więc każdy klawisz wprowadzałby dziewięć minus liczba, która ma być odejmowane) i naciśnięcie specjalnego przycisku zakładałoby przeniesienie do obliczenia. Tak więc na sześciocyfrowej maszynie, aby odjąć 1234 od wartości, operator naciskałby klawisze, które normalnie wskazywałyby „998,765” i naciskał przycisk, aby dodać tę wartość plus jeden do trwającego obliczenia. Arytmetyka uzupełnienia do dwóch jest po prostu binarnym odpowiednikiem wcześniejszej arytmetyki „uzupełnienia do dziesięciu”.

Zaletą wykonywania odejmowania metodą komplementarną jest zmniejszenie
złożoności sprzętowej. Nie jest potrzebny inny obwód cyfrowy do dodawania i odejmowania. Oba dodawanie i odejmowanie odbywa się tylko przez sumator.

Główną zaletą reprezentacji uzupełnienia do dwóch, o której jeszcze nie wspomniano, jest to, że niższe bity sumy, różnicy lub iloczynu uzupełnienia do dwóch są zależne tylko od odpowiednich bitów argumentów. Powodem, dla którego 8-bitowa wartość ze znakiem -1 jest 11111111taka, że ​​odjęcie dowolnej liczby całkowitej, której najniższe 8 bitów pochodzi 00000001od dowolnej liczby całkowitej, której najniższe 8 bitów 0000000daje liczbę całkowitą, której najniższe 8 bitów to11111111. Matematycznie wartość -1 byłaby nieskończonym ciągiem 1, ale wszystkie wartości w zakresie określonego typu liczb całkowitych będą albo wszystkie 1 lub wszystkie 0 poza pewnym punktem, więc komputer może „rozszerzyć znak” najbardziej znaczący bit liczby, tak jakby reprezentował nieskończoną liczbę 1 lub 0.

Uzupełnienie do dwóch jest prawie jedyną reprezentacją liczb podpisanych, która działa dobrze, gdy mamy do czynienia z typami większymi niż naturalny rozmiar słowa maszyny binarnej, ponieważ podczas wykonywania dodawania lub odejmowania kod może pobrać najmniejszą część każdego operandu, obliczyć najniższą część wynik i zapisz go, a następnie załaduj kolejny fragment każdego operandu, oblicz następny fragment wyniku i zapisz go itp. Tak więc nawet procesor, który wymaga wszystkich dodatków i odejmowań, aby przejść przez pojedynczy 8-bitowy rejestr potrafi obsługiwać 32-bitowe liczby ze znakiem stosunkowo wydajnie (oczywiście wolniej niż z rejestrem 32-bitowym, ale nadal wykonalne).

Podczas korzystania z dowolnych innych podpisanych reprezentacji dozwolonych przez standard C, na każdy bit wyniku może potencjalnie wpływać dowolny bit argumentów, powodując konieczność trzymania całej wartości w rejestrach na raz lub wykonania obliczeń z dodatkowym krok, który przynajmniej w niektórych przypadkach wymagałby odczytania, modyfikacji i przepisania każdej porcji wyniku.

Istnieją różne typy reprezentacji:

1. reprezentacja bez znaku
2. podpisana reprezentacja numeru
3. reprezentacja dopełniacza
4. Reprezentacja uzupełnienia do dwóch

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

-Podpisana liczba reprezentuje liczbę dodatnią i ujemną. W reprezentacji liczb podpisanych bit MSB reprezentuje bit znaku, a bity spoczynkowe reprezentują liczbę. Gdy MSB wynosi 0, oznacza, że ​​liczba jest dodatnia, a gdy MSB wynosi 1, oznacza, że ​​liczba jest ujemna.

Problem z reprezentacją podpisanego numeru polega na tym, że istnieją dwie wartości 0.

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

Ale jeśli użyjemy reprezentacji dopełniacza Two, wtedy będzie tylko jedna wartość dla 0, dlatego reprezentujemy liczby ujemne w formie dopełniacza dwóch.

Źródło: Dlaczego liczby ujemne są przechowywane w postaci dwóch uzupełnień w bajtach ggababajtów

Jedną zadowalającą odpowiedzią na to, dlaczego Uzupełnienie Two2 jest używane do reprezentowania liczb ujemnych, a nie Uzupełnienie One, to fakt, że Uzupełnienie Two rozwiązuje problem wielokrotnych reprezentacji 0 i potrzebę przeniesienia które istnieją w uzupełniającym układzie reprezentowania ujemnego liczby.

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

Aby przejść do końca, odwiedź https://en.wikipedia.org/wiki/End-around_carry