Avatar
Lukas C#
Redaktor
Avatar
Lukas C#:

Ahojte, mohl by mi někdo vysvětlit, proč (při bitovém sčítání dvou čísel x,y ve dvojkovém doplňku) platí:
NOT( x + (-1) ) == - x , dále NOT( NOT(x) + y ) == x - y a NOT( x + NOT(y) ) == y - x ? Vím, že pokud chci odečíst dvě (kladná) čísla, tak musím odělat dvojkový doplněk toho druhého a pak je sečíst, ale tady to nějak nevidím.

 
Odpovědět 18. ledna 17:13
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Lukas C#
Drahomír Hanák:

Číslo převedeš na dvojkový doplněk tak, že zneguješ bity čísla a přičteš k němu 1 (operace + je bitové sčítání s přenosem):

(-x) = NOT(X) + 1

Přičtením (-1) k oběma stranám: (-x) + (-1) = NOT(x) + 1 + (-1) = NOT(x)

Z toho dostaneš pro první vztah: NOT(x + (-1)) = -(x + (-1)) + (-1) = (-x) + 1 + (-1) = -x

Pro druhý vztah: NOT(NOT(x) + y) = -(NOT(x) + y) + (-1) = -((-x) + (-1) + y) + (-1) = x + 1 + (-y) + (-1) = x - y

Třetí vztah je to samé.

Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
 
Nahoru Odpovědět  +1 18. ledna 18:02
Avatar
B42P6
Člen
Avatar
B42P6:

Ahoj, ja tomu chápem tak že -x je v binárke reprezentovaný ako -x+2ⁿ kde n je počet binárnych číslic. Prečo? Vysvetlím to na desiatkovej sústave. Predstav si že idem odčítať 2 čísla, napríklad 6-3, a môžem iba sčítať a odčítať(ale iba od čísla 10). Ako to spravím? Vypočítam 10-3 a nahradím to za druhé číslo a zmením znamienko na +, takže máme 6+7(13).následne odoberiem jednotku a máme výsledok (mám 13 odoberiem jednotku, mám 3). Ako to funguje? Vlastne som iba pripočítal 10 k príkladu ,(to bolo to 10-3, čo je to isté ako -3+10 (pripočítavam 10 k príkladu)), a od výsledku som zase iba 10 odpočítal (odobral som jednotku). Čiže som si iba požičal 10 a potom som ju zase vrátil. V Binárke je to to isté ibaže pripočítaš 2ⁿ (n je počet číslic), zjednodušene povedané musíš zistiť koľko chýba do 2ⁿ (čo sa vlastné rovná 2ⁿ-x). Ako? Takže 2ⁿ-1 (samé jednotky) zistíš tým že číslo x NOT-neš. Pravdepodobne vieš ako sa sčítajú 2 čísla. Takže ak si to zoberieš tak x+NOT(x)=2ⁿ-1 (samé jednotky).

Pre lepšie pochopenie
x= 1001
NOT(x)= 0110
x+NOT(x)= 1111

Takže vieš ako získať 2ⁿ-1. Teraz už stačí iba pripočítať jednotku a zistíš koľko chýba do 2ⁿ. Teraz si získal -x+2ⁿ, čo sa rovná 2ⁿ-x (2ⁿ-x je vlastne to čo nám chýba do 2ⁿ). Prečo to je tak? Spomeň si na príklad v desiatkovej sústave kde som mohol len sčítať a odčítať iba od čísla 10. To isté teraz urobím v binárke. Idem odčítať 6(0110)-3(0011). K číslu -3 pripočítam 2⁴ ("n" som nahradil počtom binárnych číslic(4)). Ak si spomenieš -3+2⁴ je to isté ako 2⁴-3, 2⁴-3 zistíš tým že najprv zistíš koľko chýba do 2⁴-1(samé jednotky), čo je NOT(x)=1100, a následne pripočítaš jednotku (0001), čo je 1101. Takže teraz si pripočítal 2⁴ k -3. Vypočítaj 0110 (6)+1101(to je to čo sme zistili) (to sa rovná 10011). Takže teraz si zistil 6-3+2⁴. Ako ale odpočítaš 2⁴? Jednoducho, iba odoberieš prvú jednotku (pretože 2⁴=10000). Odoberieš jednotku a máš 00011, Po odobratí jednotky si zistil 6-3+2⁴-2⁴, Čo je to isté ako 6-3. Takže celá myšlienka dvojkového doplnku je vlastne to že si vždy požičiaš nejaké číslo (pripočítať 2ⁿ k -x je ako si videl jednoduché), a to číslo potom odčítaš (čo je tiež veľmi jednoduché (iba odoberieš jednotku)). Pri dvoch zvyšných príkladoch to je tiež o tom istom lenže si požičiavaš iné číslo.
http://mathforum.org/…w/55949.html

Editováno 18. ledna 18:36
Nahoru Odpovědět 18. ledna 18:34
'long long long' is too long for GCC
Avatar
Lukas C#
Redaktor
Avatar
Odpovídá na Drahomír Hanák
Lukas C#:

Perfektní, chvíli mi to trvalo pobrat, ale díky moc :-)

 
Nahoru Odpovědět 18. ledna 22:14
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.