Ones komplement - Ones' complement
| Bits | Osignerat värde |
Ones' komplement värde |
|---|---|---|
| 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 |
De komplement av ett binärt tal är det värde som erhålls genom att invertera alla bitar i den binära representationen av numret (byta 0 och 1). Denna matematiska operation är främst av intresse för datavetenskap , där den har olika effekter beroende på hur en specifik dator representerar siffror.
Ett ens komplementsystem eller ett komplement aritmetik är ett system där negativa tal representeras av det inversa av de binära representationerna av deras motsvarande positiva tal. I ett sådant system negeras ett tal (omvandlat från positivt till negativt eller tvärtom) genom att beräkna dess komplement. En N-bitars kompletterande siffersystem kan endast representera heltal i intervallet - (2 N − 1 −1) till 2 N − 1 −1 medan tvås komplement kan uttrycka −2 N − 1 till 2 N − 1 −1. Det är en av tre vanliga representationer för negativa heltal i mikroprocessorer , tillsammans med två komplement och teckenstorlek .
De komplementära binära siffersystemet kännetecknas av att bitkomplementet för vilket heltal som helst är det aritmetiska negativet av värdet. Det vill säga att invertera alla bitar i ett tal (det logiska komplementet) ger samma resultat som att subtrahera värdet från 0.
Många tidiga datorer, inklusive UNIVAC 1101 , CDC 160 , CDC 6600 , LINC , PDP-1 och UNIVAC 1107 , använde komplement aritmetik. Efterföljare av CDC 6600 fortsatte att använda ens komplementräkning fram till slutet av 1980-talet, och ättlingarna till UNIVAC 1107 ( UNIVAC 1100/2200-serien ) gör fortfarande, men majoriteten av moderna datorer använder två komplement .
Nummerrepresentation
Positiva tal är samma enkla, binära system som används av två komplement och teckenstorlek. Negativa värden är bitkomplementet för motsvarande positivt värde. Det största positiva värdet kännetecknas av att tecknet (hög ordning) bit är av (0) och alla andra bitar är på (1). Det lägsta negativa värdet kännetecknas av att teckenbiten är 1 och alla andra bitar är 0. Tabellen nedan visar alla möjliga värden i ett 4-bitars system, från −7 till +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
Grunderna
Att lägga till två värden är enkelt. Justera helt enkelt värdena på den minst signifikanta biten och lägg till, förök alla bärningar till biten en position kvar. Om bärningen sträcker sig förbi slutet av ordet sägs den ha "lindat runt", ett tillstånd som kallas " slut-runt-bär ". När detta inträffar måste biten läggas till igen längst till höger. Detta fenomen förekommer inte i tvås komplement aritmetik.
0001 0110 22 + 0000 0011 3 =========== ==== 0001 1001 25
Subtraktion är liknande, förutom att lån, snarare än bär, sprids till vänster. Om lånet sträcker sig förbi slutet av ordet sägs det ha "lindat runt", ett tillstånd som kallas " end-around lån ". När detta inträffar måste biten subtraheras från den högsta biten. Detta fenomen förekommer inte i tvås komplement aritmetik.
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)
Det är lätt att visa att bitkomplementet av ett positivt värde är det positiva värdets negativa storlek. Beräkningen av 19 + 3 ger samma resultat som 19 - (−3).
Lägg till 3 till 19.
0001 0011 19 + 0000 0011 3 =========== ==== 0001 0110 22
Subtrahera −3 från 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).
Negativ noll
Negativ noll är villkoret där alla bitar i ett undertecknat ord är 1. Detta följer de komplementregler som gäller att ett värde är negativt när den längst till vänster är 1 och att ett negativt tal är bitkomplementet av talets storlek. Värdet beter sig också som noll vid beräkning. Att lägga till eller subtrahera negativ noll till / från ett annat värde ger det ursprungliga värdet.
Lägger till negativ noll:
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)
Subtrahera negativ noll:
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)
Negativ noll produceras enkelt i en 1: s komplementadderare. Lägg bara till det positiva och det negativa av samma storlek.
0001 0110 22 + 1110 1001 −22 =========== ==== 1111 1111 −0 Negative zero.
Även om matematiken alltid ger rätt resultat är en bieffekt av negativ noll att programvaran måste testa för negativ noll.
Undvik negativ noll
Genereringen av negativ noll blir en icke-fråga om addition uppnås med en kompletterande subtraktor. Den första operanden skickas till subtrakten omodifierad, den andra operanden kompletteras och subtraktionen genererar rätt resultat och undviker negativ noll. Det föregående exemplet lade till 22 och −22 och producerade −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
"Hörnfall" uppstår när en eller båda operanderna är noll och / eller negativa noll.
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
Att subtrahera +0 är trivialt (som visas ovan). Om den andra operanden är negativ noll är den inverterad och originalvärdet för den första operanden är resultatet. Att subtrahera −0 är också trivialt. Resultatet kan bara bli ett av två fall. I fall 1 är operand 1 -0 så resultatet produceras helt enkelt genom att subtrahera 1 från 1 vid varje bitposition. I fall 2 kommer subtraktionen att generera ett värde som är 1 större än operand 1 och en slutlån . Att slutföra lånet genererar samma värde som operand 1.
Nästa exempel visar vad som händer när båda operanderna är plus eller minus noll:
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
Detta exempel visar att av de fyra möjliga villkoren när endast adderas ± 0, kommer en adderare att producera −0 i tre av dem. En kompletterande subtraktor producerar −0 endast när båda operanderna är −0.
Se även
Referenser
- Donald Knuth : The Art of Computer Programming , Volume 2: Seminumerical Algorithms, kapitel 4.1
