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!
Odpowiedzi:
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
0010
i1001
(trzymam się 4 bitów dla rozmiaru). W uzupełnieniu tych dwóch są0010
i1111
. 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:
0001
wynosi 1, co jest oczekiwanym wynikiem „2 + (- 1)”.Jednak w metodzie „intuicyjnej” dodawanie jest bardziej skomplikowane:
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:
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:
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:
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.
źródło
how we arrived at 2s compliment the first place.
cs.cornell.edu/~tomf/notes/cps104/twoscomp.html1
wskazuje-8
, a pozostałe trzy1
y wskazać4
,2
i1
, odpowiednio, tak-8+4+2+1 = -1
.Wikipedia mówi wszystko:
Innymi słowy, dodawanie jest takie samo, niezależnie od tego, czy liczba jest ujemna.
źródło
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:
Co się stanie, jeśli spróbujemy dodać jeszcze 1 do wyniku. Spowoduje to przepełnienie.
Wynik będzie wynosił
1 0000
0 (ponieważ pracujemy z liczbami 4-bitowymi, (1 po lewej jest przepełnieniem)Więc ,
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.
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.
źródło
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).
źródło
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.
źródło
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 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
Zwykła interpretacja binarna bez znaku to:
2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
Interpretacja dopełniacza tych dwóch:
-2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
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 7 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.
źródło
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.
źródło
Aby rozwinąć inne odpowiedzi:
W uzupełnieniu do dwóch
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ł.
źródło
unsigned mul(unsigned short x, unsigned short y) { return x*y; }
[16-bit krótki; 32-bit int] czasami generuje kod, który będzie działać niepoprawnie, jeśli produkt będzie większy niż 2147483647.Czytając odpowiedzi na to pytanie, natknąłem się na ten komentarz [zredagowany].
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ą
PRZYKŁAD - poniżej zakładamy, że
char
mają 1 bajt długościshort
mają 2 bajty długościint
ifloat
mają długość 4 bajtówNależ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 szesnastkowejBD
.Następnie odczytujemy zawartość tablicy za pomocą różnych typów.
unsigned char
isigned char
unsigned short
ishort
unsigned int
,int
afloat
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_Just4Bytes
tablicyunsigned char
: 1 bajt w formacie binarnymsigned char
: 1 bajt w uzupełnieniu do 2unsigned short
: 2 bajty w zwykłym zapisie binarnymshort
: 2 bajty w uzupełnieniu do 2unsigned int
: 4 bajty w zwykłym zapisie binarnymint
: 4 bajty w uzupełnieniu do 2float
: 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!
źródło
int x = -4
, a następnie robię,printf("%d" , x)
jak to jest interpretowane? A także, jaka jest różnica międzyunsigned int
isigned int
a ...%d
i%u
to mnie denerwuje od dłuższego czasu. Dzięki.int
typówsigned
modyfikator jest domyślny. Oznacza to, żeint
isigned int
są dokładnie tego samego typu. Zatem dwie definicjeint i = -4;
isigned int i = -4;
mają to samo znaczenie.int
ma 4 bajty w uzupełnieniu do 2, aunsigned int
4 bajty w zwykłej notacji binarnej (sprawdź rzeczywisty rozmiar typu w systemie za pomocąsizeof
operatora).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 .
źródło
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).
źródło
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 .
źródło
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.
źródło
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”.
źródło
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.
źródło
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
11111111
taka, że odjęcie dowolnej liczby całkowitej, której najniższe 8 bitów pochodzi00000001
od dowolnej liczby całkowitej, której najniższe 8 bitów0000000
daje 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.
źródło
Istnieją różne typy reprezentacji:
-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
źródło
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
źródło