Ich uzupełnienie - Ones' complement
| Bity | Wartość bez znaku |
Dopełnianie wartości One |
|---|---|---|
| 0111 1111 | 127 | 127 |
| 0111 1110 | 126 | 126 |
| 0000 0010 | 2 | 2 |
| 0000 0001 | 1 | 1 |
| 0000 0000 | 0 | 0 |
| 1111 1111 | 255 | -0 |
| 1111 1110 | 254 | -1 |
| 1111 1101 | 253 | -2 |
| 1000 0001 | 129 | -126 |
| 1000 0000 | 128 | -127 |
Przez uzupełnienie ones' z binarnym jest wartością otrzymaną przez inwersję wszystkich bitów w binarnej reprezentacji liczby (przełączanie 0 i 1). Ta matematyczna operacja jest interesująca przede wszystkim w informatyce , gdzie ma różne skutki w zależności od tego, jak konkretny komputer reprezentuje liczby.
System uzupełnień do jedynek lub arytmetyka dopełnień do jedynek to system, w którym liczby ujemne są reprezentowane przez odwrotność reprezentacji binarnych odpowiadających im liczb dodatnich. W takim systemie liczba jest negowana (konwertowana z dodatniej na ujemną lub odwrotnie) przez obliczenie jej uzupełnienia. N-bitowy system liczbowy dopełnienia jedynek może reprezentować tylko liczby całkowite z zakresu od −(2 N−1 −1) do 2 N−1 −1, podczas gdy dopełnienie do dwójki może wyrażać −2 N−1 do 2 N−1 −1. Jest to jedna z trzech powszechnych reprezentacji ujemnych liczb całkowitych w mikroprocesorach , wraz z uzupełnieniem do dwóch i wielkością znaku .
Uzupełnienie do jedynek dwójkowego systemu liczbowego charakteryzuje się uzupełnieniem bitowym dowolnej wartości całkowitej będącej arytmetycznie ujemną wartością. Oznacza to, że odwrócenie wszystkich bitów liczby (dopełnienia logicznego) daje ten sam wynik, co odjęcie wartości od 0.
Wiele wczesnych komputerów, w tym UNIVAC 1101 , CDC 160 , CDC 6600 , LINC , PDP-1 i UNIVAC 1107 , używało arytmetyki uzupełnień. Następcy CDC 6600 nadal używali arytmetyki dopełnień do końca lat 80-tych, a potomkowie UNIVAC 1107 ( seria UNIVAC 1100/2200 ) nadal to robią, ale większość współczesnych komputerów używa dopełniania do dwóch .
Reprezentacja liczb
Liczby dodatnie to ten sam prosty, binarny system używany przez dopełnienie do dwójki i znak-wielkość. Wartości ujemne są uzupełnieniem bitowym odpowiedniej wartości dodatniej. Największa wartość dodatnia charakteryzuje się tym, że bit znaku (wysokiego rzędu) jest wyłączony (0), a wszystkie pozostałe bity są włączone (1). Najniższa wartość ujemna charakteryzuje się tym, że bit znaku ma wartość 1, a wszystkie pozostałe bity to 0. Poniższa tabela pokazuje wszystkie możliwe wartości w systemie 4-bitowym, od -7 do +7.
+ − 0 0000 1111 — Note that both +0 and −0 return TRUE when tested for zero 1 0001 1110 — and FALSE when tested for non-zero. 2 0010 1101 3 0011 1100 4 0100 1011 5 0101 1010 6 0110 1001 7 0111 1000
Podstawy
Dodanie dwóch wartości jest proste. Po prostu wyrównaj wartości na najmniej znaczącym bicie i dodaj, propagując dowolne przeniesienie do bitu o jedną pozycję w lewo. Jeśli przeniesienie wykracza poza koniec słowa, mówi się, że zostało "zawinięte", stan zwany " przeniesieniem na koniec ". Gdy to nastąpi, bit musi zostać dodany z powrotem w skrajnym prawym bicie. Zjawisko to nie występuje w arytmetyce uzupełnień do dwóch.
0001 0110 22 + 0000 0011 3 =========== ==== 0001 1001 25
Odejmowanie jest podobne, z tym wyjątkiem, że pożyczki, a nie przeniesienia, są propagowane w lewo. Jeśli pożyczka wykracza poza koniec słowa, mówi się, że została „zawinięta”, warunek zwany jest „ pożyczką z zakończeniem ”. Gdy to nastąpi, bit musi zostać odjęty od najbardziej prawego bitu. Zjawisko to nie występuje w arytmetyce uzupełnień do dwóch.
0000 0110 6 − 0001 0011 19 =========== ==== 1 1111 0011 −12 —An end-around borrow is produced, and the sign bit of the intermediate result is 1. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 1111 0010 −13 —The correct result (6 − 19 = -13)
Łatwo zademonstrować, że uzupełnienie bitowe wartości dodatniej jest ujemną wielkością wartości dodatniej. Obliczenie 19 + 3 daje taki sam wynik jak 19 − (−3).
Dodaj 3 do 19.
0001 0011 19 + 0000 0011 3 =========== ==== 0001 0110 22
Odejmij -3 od 19.
0001 0011 19 − 1111 1100 −3 =========== ==== 1 0001 0111 23 —An end-around borrow is produced. − 0000 0001 1 —Subtract the end-around borrow from the result. =========== ==== 0001 0110 22 —The correct result (19 − (−3) = 22).
Ujemne zero
Ujemne zero to warunek, w którym wszystkie bity w słowie ze znakiem są równe 1. Jest to zgodne z regułami dopełniania jedności, że wartość jest ujemna, gdy skrajny lewy bit to 1, a liczba ujemna jest uzupełnieniem bitowym wielkości liczby. Wartość zachowuje się również jako zero podczas obliczania. Dodanie lub odjęcie ujemnego zera do/od innej wartości daje oryginalną wartość.
Dodanie ujemnego zera:
0001 0110 22 + 1111 1111 −0 =========== ==== 1 0001 0101 21 An end-around carry is produced. + 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 + (−0) = 22)
Odejmowanie ujemnego zera:
0001 0110 22 − 1111 1111 −0 =========== ==== 1 0001 0111 23 An end-around borrow is produced. − 0000 0001 1 =========== ==== 0001 0110 22 The correct result (22 − (−0) = 22)
Ujemne zero jest łatwo wytwarzane w dodawaniu dopełniającym do jedynki. Po prostu dodaj dodatni i ujemny tej samej wielkości.
0001 0110 22 + 1110 1001 −22 =========== ==== 1111 1111 −0 Negative zero.
Chociaż matematyka zawsze daje prawidłowe wyniki, efektem ubocznym ujemnego zera jest to, że oprogramowanie musi testować ujemne zero.
Unikanie ujemnego zera
Generowanie ujemnego zera nie stanowi problemu, jeśli dodawanie jest osiągane za pomocą dopełniającego odejmowania. Pierwszy argument jest przekazywany do odejmowania niezmodyfikowany, drugi argument jest uzupełniany, a odejmowanie generuje poprawny wynik, unikając ujemnego zera. Poprzedni przykład dodał 22 i -22 i wyprodukował -0.
0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22 + 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22 =========== ==== but =========== ==== likewise, =========== === but =========== === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0
„Przypadki narożne” powstają, gdy jeden lub oba argumenty są zerowe i/lub ujemne.
0001 0010 18 0001 0010 18
− 0000 0000 0 − 1111 1111 −0
=========== ==== =========== ====
0001 0010 18 1 0001 0011 19
− 0000 0001 1
=========== ====
0001 0010 18
Odejmowanie +0 jest trywialne (jak pokazano powyżej). Jeśli drugi operand jest ujemnym zerem, jest on odwracany, a wynikiem jest pierwotna wartość pierwszego operandu. Odejmowanie -0 jest również trywialne. Wynikiem może być tylko 1 z dwóch przypadków. W przypadku 1, argument 1 wynosi -0, więc wynik jest uzyskiwany po prostu przez odjęcie 1 od 1 na każdej pozycji bitowej. W przypadku 2 odejmowanie wygeneruje wartość o 1 większą niż operand 1 i pożyczka na koniec . Zakończenie wypożyczenia generuje taką samą wartość jak operand 1.
Następny przykład pokazuje, co się dzieje, gdy oba operandy mają wartość plus lub minus zero:
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0
+ 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0
=========== ==== =========== ==== =========== ==== =========== ====
0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1
+ 0000 0001 1
==================
1111 1111 −0
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 − 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0 =========== ==== =========== ==== =========== ==== =========== ==== 1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0 − 0000 0001 1 =========== ==== 0000 0000 0
Ten przykład pokazuje, że z 4 możliwych warunków przy dodawaniu tylko ±0, sumator wygeneruje -0 w trzech z nich. Odejmowanie uzupełniające da -0 tylko wtedy, gdy oba argumenty mają wartość -0.
Zobacz też
Bibliografia
- Donald Knuth : Sztuka programowania , tom 2: Seminumerical Algorytmy, rozdział 4.1