Комплемент двојке

Комплемент двојке, допунски код, потпуни комплемент или други комплемент представља математичку операцију над бинарним бројевима, као и репрезентацију означених бројева базирану на тим операцијама.

Комплемент двојке неког Н-битног броја добија се као допуна до броја 2^Н, односно вредност комплемента двојке за неки број добија се одузимањем тог броја од броја 2^Н. Еквивалентно овој методи, комплемент двојке неког броја може се добити и помоћу комплемента јединице.

Најпре се израчуна први комплемент броја тако што се свака бинарна цифра полазног броја промени (нула у јединицу, а јединица у нулу), па се затим добијеном бинарном броју дода јединица. Сабирање са јединицом обавља се по принципима бинарног сабирања.Бинарни бројеви се сабирају исто као и децимални, с тим што се пренос на више место догађа када збир премаши 1, а не 9, као што је у децималном систему. Други комплемент негативног бинарног броја добија се тако што се све нуле и прва јединица с десне стране препишу, а остале цифре се инвертују. У комплементу двојке може се представити било који целобројни означени број из интервала -2^Н-1 до 2^Н-1-1, док се у комплементу јединице могу представити само бројеви из интервала од -(2^Н-1-1) до 2^Н-1-1.

Две главне предности представљања броја у комплементу двојке: Основне аритметичке операције као што су сабирање, одузимање и множење су исте као и за неозначене целобројне бројеве све док су улазни подаци записани у истом броју бита и док се свако прекорачење преко тог броја битова искључује из решења.

Постоји само једна представа броја 0, чиме је избегнута конфузија која се ствара у комплементу јединице приликом дефинисања нуле два пута (једном као позитивног, а други пут као негативног броја.)

Приказ са 8 бита	Вредност у неозначеном систему	Вредност у комплемент двојке
1111 1111	255	-1
1111 1110	254	-2
1000 0010	130	-126
1000 0001	129	-127
1000 000	128	-128
0111 1111	127	127
0111 1110	126	126
0000 0010	2	2
0000 0001	1	1
0000 0000	0	0

Комплемент

Комплемент је појам који се често користи када се говори о бројевним системима. Практични смисао увиђа се приликом приказивања негативних бројева и одузимања бројева, односно приликом реализације ове операције кроз операцију сабирања. Комплементи позитивних бројева су исти као и ти сам бројеви. Најопштија, упрошћена дефиниција комплемента била би да је то допуна датог броја до неке унапред дефинисане вредности. У бинарном бројном систему дефинисана су само два комплемента и оба су од практичног значаја. Комплемент јединице (као комплемент највеће цифре) и комплемент двојке (као комплемент основе система).

Конвертовање из комплемента двојке

Систем комплемента двојке кодира позитивне и негативне бројеве у бинарној презентацији. Тежина сваког бита је степен броја два, осим за најважнији бит (МСБ), чија тежина је негатив од одговарајућег степена броја два.

Вредност w Н-битног интегера $a_{N-1}a_{N-2}...a_{0}$ дата је помоћу следеће формуле:

$w=-a_{N-1}2^{N-1}+\sum _{i=0}^{N-2}a_{i}2^{i}$

Најважнији бит одређује знак броја и понекад се назива знак бит. За разлику од сигн-анд-магнитуде презентације, сигн бит такође има тежину −(2^Н − 1) показану изнад. Коришћењем Н битова, сви цели бројеви од −(2^Н − 1) то 2^Н − 1 − 1 могу бити презентовани.

Конверзија из комплемента двојке

У нотацији комплемента двојке, не-негативни број је приказан у својој уобичајеној презентацији; у овом случају. најважнији бит је 0. Опсег приказаних бројева није исти као код неозначених (унсигнед) бинарних бројева. На пример, 8-битни неозначени број може представљати вредности између 0 и 255 (11111111). 8-битни број комплемента двојке може да представља целе позитивне бројеве од 0 до 127 (01111111), јер остатак комбинација битова са најважнијим битом сетованим на '1' представља целе негативне бројеве од -1 до -128. Операција комплемента двојке је адитивно инверзна операција, па су негативни бројеви представљени другим комплементом апсолутне вредности.

Конверзија из комплемента јединице

Да би се добио комплемент двојке бинарног броја, битови се инвертују коришћењем бинарне НОТ операције; резултујућој вредности се додаје 1, игноришући оверфлоw преступ који се појављује када се узима комплемент двојке броја 0. На пример, користећи 1 бајт (= 2 нибла = 8 битова), децимални број 5 је приказан као

0000 0101

Најважнији бит је 0, па ова комбинација представља не-негативни број. За конверзију у -5 у нотацији комплемета двојке, битови су инвертовани; 0 постаје 1, и 1 постаје 0;

1111 1010

У овом тренутку, приказани број представља -5 у комплементу јединице. Како би се добио комплемент двојке, 1 се додаје резултату, дајући:

1111 1011

Резултат је означени бинарни број који представља децималну вредност -5 у форми комплемента двојке. Најважнији бит је 1, па је приказана вредност негативна.

Комплемент двојке негативног броја је његова одговарајућа позитивна вредност. На пример, инвертовање битова од -5 (изнад) даје:

0000 0100

Додавањем јединице даје коначну вредност:

0000 0101

Комплемент двојке броја 0 је 0: Инвертовањем сви битови постају 1, а затим додавањем јединице, сви битови поново постају нуле (оверфлоw преступ се игнорише). Комплемент двојке најнегативнијег броја који се може приказати (на пример број са сетованим најважнијим битом и свим осталим битовима на нули) је исти тај број. Из овога се закључује да постоји још један додатни негативан број.

Одузимање од 2^Н

Збир броја и његовог комплемента јединице је Н-битна реч са свим битовима вредности 1, која је 2^Н-1 Додавање броја његовом комплементу двојке резултује сетовањем Н најнижих битова на 0 и царрy бита на 1, где царрy бит има тежину 2^Н. Тако, у неозначеној бинарној аритметици вредност комплемента двојке негативног броја x* од позитивног x задовољава једнакост x* = 2^Н − x

На пример, да би смо пронашли 4-битну презентацију броја -5

x = 5₁₀ па је x = 0101₂

са Н = 4:

x* = 2^Н − x = 2⁴ − 5₁₀ = 10000₂ − 0101₂=1011₂

Прорачун може бити урађен комплетно у декадном систему, конвертујући у бинарни систем на самом крају.

x* = 2^Н − x = 2⁴ − 5₁₀ = 11₁₀ = 1011₂

Конвертовање од ЛСБ до МСБ

Пречица за ручну конверзију бинарног броја у његов комплемент двојке је започињење код најмање важног бита (ЛСБ) и копирање свих нула (радећи од ЛСБ према МСБ) све док се не дође до прве јединице; та јединица се копира, а преостали битови се инвертују (Оставите МСБ као 1 ако је иницијални број био у сигн-анд-магнитуде презентацији). Ова пречица нам омогућује да претворимо број у његов комплемент двојке без претходног прављења његовог комплемента јединице. На пример: комплемент двојке од "0011 1100" је "1100 0100", где су подвучене цифре које се не мењају опрацијом копирања (док је остатак цифара инвертован). У компјутерској технологији, ова метода није бржа од "комплемент и додај један" методе; Обе методе захтевају секвенцијални рад са десна на лево, пропагирајући логичке промене. Метода комплементирања и додавања јединице може бити убрзана помоћу стандардног царрy лоок-ахеад аддер кола; ЛСБ према МСБ метода може бити убрзана сличном логичком трансформацијом.

Екстензија знака

Главни чланак: Екстензија знака

Децимално 7-битна нотација:	42	1010110	1101 0110
8-битна нотација:	−42	0101010	0010 1010

Понављање сигн бита у 7 и 8 битним интегерима коришћењем комплемента двојке

Претварањем комплемента двојке неког броја са одређеним бројем битова у неки са више битова (на пример копирање са 1 бајтне променљиве у двобајтну променљиву), најважнији бит мора бити поновљен у свим додатним и нижим битовима. Неки процесори имају инструкцију да ово обаве у једној инструкцији. На другим процесорима мора бити постављен услов са кодом за сетовање релевантних битова или бајтова. Слично, када је комплемент двојке неког броја шифтован на десно, најважнији бит, који садржи информацију о вредности и знаку мора бити очуван. Када се шифтује у лево, 0 улази унутра са десне стране. Ова правила чувају општу семантику да лева шифтовања множе број са сва и да десна шифтовања број деле са два. I шифтовање и дуплирање прецизности су важни за неке мултипликацијске алгоритме. Може се приметити да су за разлику од сабирања и одузимања, проширње прецизности и десно шифтовање урађени на један начин за означене, а на други начин за неозначене бројеве.

Најнегативнији број

Са само једним изузетком, почев од било ког броја у комплементу двојке, уколико се сви битови инвертују и дода 1, добија се комплемент двојке негатива тог броја. Позитивна 12 постаје негативна 12, позитивна 5 постаје негативна 5, нула постаје нула (+оверфлоw), итд.

−128 1000 0000 инвертовани битови 0111 1111 додавање јединице 1000 0000 Комплемент двојке броја -128 даје исти 8 битни бинарни број. Комплемент двојке минималног броја у опсегу неће имати жељени ефекат од негације броја. На пример, комплемент двојке од -128 у 8-битном систему резултује истим бинарним бројем. Ово је због тога [то позитивна вредност 128 не може бити представљена са 8-битним означеним бинарним бројем.

Аритметичке операције

Сабирање

Сабирање бројева у комплементу двојке не тражи никакво посебно процесирање ако операнди имају супротан знак: Знак резултата је одређен аутоматски. На пример, сабирање 15 и -5:

 11111 111   (carry)
  0000 1111  (15)
+ 1111 1011  (−5)
==================
  0000 1010  (10)

Овај процесс зависи од ограничавања на 8 битну прецизност; царрy на (непостојећи) девети најважнији бит је игнорисан, резултујући са аритметички тачним 1010.

Последња два бита у царрy реду (читајући са десна на лево) садрже виталне информације: да ли је прорачун донео аритметички преступ, број превелик да би био приказан у бинарном систему (у овом случају већи од 8 бита). Стање преступа постоји када су ова последња два бита различита један од другог. Као што је већ наведено, знак броја је кодиран у најважнијем биту резултата. Другим речима, ако су оба лева царрy бита (они са леве стране на самом врху нашег примера) 1 или су оба 0, резултат је исправан; ако си лева два царрy бита "1 0" или "0 1", појавио се знак оверфлоwа. XОР операција над овим битовима може брзо да нам одреди да ли постоји услов преступа. На пример, означено 4-битно сабирање 7 и 3:

 0111   (carry)
  0111  (7)
+ 0011  (3)
=============
  1010  (−6)  invalid!

У овом случају, крајње лева два (МСБ) царрy бита су "01", што значи да је дошло до преступа сабирања комплемента двојке. Тако је 10102=1010 изван дозвољеног опсега од -8 до 7.

Уопштено, било која два Н-битна броја могу бити сабрана без преступа, претходним проширењем оба на Н+1 бит, и онда их сабрати као на примеру. Н+1 бит резултат је довољно велик да прикаже било који могући збир (Н=5 комплемент двојке може да прикаже вредности од -16 до 15) па се преступ никада неће појавити. Онда је могуће, уколико се то жели, скратити резултат назад на Н битова чувајући вредност ако и само ако је одбачени бит екстензија одговарајућег знака остатка резултујућих битова. Ово омогућује други метод детектовања преступа који је еквивалентан методи поређења царрy битова, само што може бити једноставнији за примену у неким ситуацијама, јер не захтева приступ детаљима сабирања.

...................................................................................................................

Одузимање

Компјутери обично користе методу комплемента да би инплементирали одузимање. Коришћење комплемента за одузимање је блиско везано за коришћење комплемената за приказ негативних бројева, јер комбинација дозвољава све знаке операнада и резултата; такође, директно одузимање ради и са бројевима комплемента двојке. Као и сабирање, предност коришћења комплемента двојке је у елиминацији анализе знака операнада како би се одредило да ли је неопходно сабирање или одузимање. На пример одузимање -5 од 15 је у ствари сабирање 5 и 15. Ово је скривено презентацијом комплемента двојке:

 11110 000   (borrow)
  0000 1111  (15)
− 1111 1011  (−5)
  ===========
  0001 0100  (20)

Преступ је откривен на исти начин као и за сабирање, постматрањем последња два лева (најважнија) бита од позајмице; преступ се појавио уколико су различити.

Други пример је операција одузимања где је резултат негативан: 15-35=-20:

 11100 000   (borrow)
  0000 1111  (15)
− 0010 0011  (35)
  ===========
  1110 1100  (−20)

Као и код сабирања, преступ код одузимања може бити избегнут (или откривен после операције) повећањем броја битова оба улаза за по један бит.

..........................................................................................................................................

Множење

Производ два Н-битна броја захтева 2Н битова да би садржао све могуће вредности. Уколико је прецизност два операнда у комплементу двојке дуплирана пре множења, директно множење (одбацујући вишак битова изван те прецизности) ће дати тачан резултат. На пример, узмимо 6 x -5 = -30. Прво, прецизност је проширена са 4 бита на 8. Потом су бројеви помножени, одбацујући битове иза 8 (приказаних као 'x'):

    00000110  (6)
*   11111011  (−5)
============
         110
        1100
       00000
      110000
     1100000
    11000000
   x10000000
  xx00000000
============
  xx11100010

Ово је врло неефикасно; Дуплирајући прецизност унапред, сва сабирања морају бити дупле прецизности и најмање дупло више делимичних производа је потребно него за ефикасније алгоритме имплементиране у компјутерима. Неки мултипликациони алгоритми су пројектовани за комплемент двојке, рецимо Боотх ов мултипликациони алгоритам. Методе за множење сигн-магнитуде бројева не функционишу са бројевима у комплементу двојке без адаптације. Обично нема проблема када је мултипликант (број који се више пута сабира како би се добио производ) негативан; Потребно је тачно поставити почетне битове производа када је множилац негативан. Најчешће две методе за прилагођење алгоритама како би прихватили бројеве у комплементу двојке су:

   Prvo proverite da da li je množilac negativan. Ako jeste, negirajte oba operanda pre množenja)

Множилац постаје позитиван па ће алгоритам радити. Пошто су оба операнда негирана, резултат ће још увек имати тачан знак

   Oduzimanje delimičnog proizvoda nastalog od MSB (pseudo znak bit) umesto sabiranja kao drugi delimični proizvodi. Ova metoda zahteva multiplikantovo proširenje znak bita za jednu poziciju, kako bi bio sačuvan za desne šift akcije. 

Као пример друге методе, узмимо општи адд-анд-схифт алгоритам за множење. Уместо шифтовања делимичних производа на лево као што се ради са оловком и папиром, акумулирани производ је померен десно, у други регитар који ће евентуално држати мање важну половину производа. Пошто се најмање важни битови нису променили једном када су израчунати, додавања могу бити једноструке прецизности акумулирајући у регистру оно што ће евентуално држати најважнију половину производа. У следећем примеру, поново множећи 6 са -5, два регистра и проширен бит знака су подељени са "|":

0 0110  (6)  (multiplikant sa proširenim znako bitom)
× 1011 (−5)  (množilac)
=|====|====
0|0110|0000  (prvi delimični proizvod (krajnji desni bit je 1))        
0|0011|0000  (šift desno, čuvajući prošireni znak bit)               
0|1001|0000  (sabiranje drugog delimičnog proizvoda (sledeći bit je 1))              
0|0100|1000  (šift desno, očuvanje proširenog znak bita)              
0|0100|1000  (sabiranje trećeg delimičnog proizvoda: 0 pa nema promene)              
0|0010|0100  (šift desno, očuvanje proširenog znak bita)              
1|1100|0100  (oduzimanje poslednjeg delimičnog proizvoda jer je od znak bita)              
1|1110|0010  (šift desno, očuvanje proširenog znak bita)              

|1110|0010 (одбацивање проширеног знак бита, давење коначног одговора, -30)