Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–1
Dodawanie i odejmowanie w systemach naturalnych
β
β
}
,...,
,
,...,
{
,
}
,...,
,
,...,
{
0
1
1
0
1
1
m
k
m
k
y
y
y
y
x
x
x
x
−
−
−
−
=
=
Y
X
⇓ ⇓
1
+
±
=
±
±
i
i
i
i
i
c
s
c
y
x
β
⇓
0
=
−
m
c
β
}
,...,
,
,...,
{
0
1
1
m
k
s
s
s
s
−
−
=
S
})
1
,
0
{
}
1
,
0
{
(
}
1
,...,
1
,
0
{
,
,
1
∈
⇒
∈
⇒
−
∈
+
i
i
i
i
i
c
c
s
y
x
β
c
k
−2
x
1–m
s
1–m
c
2–m
y
1–m
Σ
s
k
−1
c
k
−1
c
k
y
k
−1
x
k
−1
Σ
x
–m
s
–m
c
–m
c
1–m
y
–m
Σ
s
k
−2
y
k
−2
x
k
−2
Σ
Schemat dodawania/odejmowania wielopozycyjnego
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–2
Poprawność dodawania i odejmowania w systemach naturalnych
β
β
}
,...,
,
,...,
{
,
}
,...,
,
,...,
{
0
1
1
0
1
1
m
k
m
k
y
y
y
y
Y
x
x
x
x
X
−
−
−
−
=
=
=
=
Y
X
⇓
1
+
±
=
±
±
i
i
i
i
i
c
s
c
y
x
β
⇓
|
}
,...,
,
,...,
{
|
0
1
1
β
m
k
s
s
s
s
Y
X
−
−
=
±
=
±
Y
X
!!
})
1
,
0
{
}
1
,
0
{
(
}
1
,...,
1
,
0
{
,
,
1
∈
⇒
∈
⇒
−
∈
+
i
i
i
i
i
c
c
s
y
x
β
Wynikiem dodawania lub odejmowania pozycyjnego (przy
0
=
−
m
c
) jest
∑
∑
−
−
=
+
−
−
=
−
±
=
±
=
±
1
1
1
)]
(
[
)
(
k
m
i
i
i
i
i
k
m
i
i
i
i
c
c
s
y
x
Y
X
β
β
β
,
k
k
k
k
k
m
i
i
i
k
m
i
i
i
i
i
k
m
i
i
i
c
S
c
s
c
c
s
Y
X
β
β
β
β
β
β
±
=
±
=
−
±
=
±
∑
∑
∑
−
−
=
−
−
=
+
+
−
−
=
1
1
1
1
1
)
(
poprawność dodawania
)
0
(
)
(
1
(
0
<
−
∧
>
+
⇒
=
⇒
<
≤
k
k
k
k
k
k
k
c
S
c
S
c
S
β
β
β
β
(
)
1
=
k
c
– nadmiar (wynik przekracza zakres)
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–3
Dodawanie i odejmowanie w systemach uzupełnieniowych
∑
−
−
=
−
−
+
−
−
+
−
=
1
1
1
1
)
(
}
,
,...,
{
k
m
i
i
i
k
m
m
k
x
R
x
x
x
x
β
ϕ
gdzie
)
)
1
2
(
sgn
1
(
)
(
1
2
1
1
+
−
+
=
−
−
β
ϕ
k
k
x
x
,
m
k
R
−
−
=
δβ
β
(
δ
= 1 lub 0)
U
U
Y
X
}
,...,
,
,...,
{
,
}
,...,
,
,...,
{
0
1
1
0
1
1
m
k
m
k
y
y
y
y
x
x
x
x
−
−
−
−
=
=
⇓ ⇓
1
+
±
=
±
±
i
i
i
i
i
c
s
c
y
x
β
⇓
0
=
−
m
c
Y
X
S
Y
X
S
U
±
=
⇔
±
=
=
−
−
}
,...,
,
,...,
{
0
1
1
m
k
s
s
s
s
Wynik działania powinien da
ć się zapisać w postaci
V
+
=
±
S
Y
X
gdzie
∑
−
−
=
−
−
−
+
−
=
=
1
1
0
1
1
)
(
}
,...,
,
,...,
{
|
|
k
m
i
i
i
k
m
k
s
R
s
s
s
s
s
β
ϕ
U
S
, V – nadmiar
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–4
Poprawność dodawania i odejmowania w systemach uzupełnieniowych
Skutkiem wykonania działa
ń zgodnie z regułą dodawania / odejmowania jest
∑
−
−
=
−
−
=
±
+
±
−
=
±
1
1
1
)
(
)]
(
)
(
[
|
|
|
|
k
m
i
i
i
i
k
k
y
x
R
y
x
β
ϕ
ϕ
Y
X
∑
−
−
=
+
−
−
−
±
+
±
−
=
1
1
1
1
)]
(
[
)]
(
)
(
[
k
m
i
i
i
i
i
k
k
c
c
s
R
y
x
β
β
ϕ
ϕ
,
sk
ąd przy
0
=
−
m
c
otrzymamy
k
k
k
m
i
i
i
k
k
c
s
R
y
x
β
β
ϕ
ϕ
±
+
±
−
=
±
∑
−
−
=
−
−
1
1
1
)]
(
)
(
[
|
|
|
|
Y
X
Z porównania wzorów wynika
)
(
))]
(
)
(
(
)
)
(
[(
|
|
|
|
|
|
1
1
1
R
c
R
y
x
c
s
k
k
k
k
k
k
−
±
±
−
±
+
=
±
−
−
−
β
ϕ
ϕ
ϕ
S
Y
X
))
(
)
(
(
)
)
(
(
1
1
1
−
−
−
±
−
±
=
k
k
k
k
y
x
c
s
v
ϕ
ϕ
ϕ
– wska
źnik nadmiaru
m
k
k
k
c
R
c
−
=
−
β
δ
β
)
(
– korekcja wyniku (przeniesienie okr
ęŜne)
•
w systemie pełnym zb
ędna, bo
δ
= 0,
•
w systemie niepełnym – c
k
na najni
Ŝszej pozycji (
δ
= 1)
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–5
Nadmiar w dodawaniu w systemach uzupełnieniowych
)]
(
)
(
[
]
)
(
[
1
1
1
−
−
−
+
−
+
=
k
k
k
k
y
x
c
s
v
ϕ
ϕ
ϕ
– znaki operandów dodatnie
1
,
0
2
1
1
1
−
≤
≤
−
−
β
k
k
y
x
(
0
)
(
)
(
1
1
=
+
−
−
k
k
y
x
ϕ
ϕ
):
•
albo
1
0
2
1
1
1
1
−
≤
+
+
≤
−
−
−
β
k
k
k
c
y
x
⇒
0
=
k
c
,
0
)
(
1
=
−
k
s
ϕ
, ⇒ v = 0
•
albo
1
1
1
1
2
1
−
≤
+
+
≤
−
−
−
β
β
k
k
k
c
y
x
⇒
0
=
k
c
,
1
)
(
1
=
−
k
s
ϕ
⇒ v = 1
– znaki operandów ujemne
1
,
1
1
2
1
−
≤
≤
−
−
β
β
k
k
y
x
(
2
)
(
)
(
1
1
=
+
−
−
k
k
y
x
ϕ
ϕ
):
•
1
1
1
1
2
1
−
+
≤
+
+
≤
+
−
−
−
β
β
β
β
k
k
k
c
y
x
⇒
1
=
k
c
,
1
)
(
1
=
−
k
s
ϕ
⇒ v = 0
•
1
2
1
1
1
1
−
+
≤
+
+
≤
−
−
−
β
β
β
k
k
k
c
y
x
⇒
1
=
k
c
,
0
)
(
1
=
−
k
s
ϕ
⇒ v =
−
1
– znaki operandów ró
Ŝne (
1
)
(
)
(
1
1
=
+
−
−
k
k
y
x
ϕ
ϕ
):
•
albo
)
1
(
2
1
1
1
1
−
+
≤
+
+
≤
−
−
−
β
β
β
k
k
k
c
y
x
⇒
1
=
k
c
,
0
)
(
1
=
−
k
s
ϕ
⇒ v = 0
•
albo
1
1
1
1
2
1
−
≤
+
+
≤
−
−
−
β
β
k
k
k
c
y
x
⇒
0
=
k
c
,
1
)
(
1
=
−
k
s
ϕ
⇒ v = 0
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–6
Nadmiar w odejmowaniu w systemach uzupełnieniowych
)]
(
)
(
[
]
)
(
[
1
1
1
−
−
−
−
−
−
=
k
k
k
k
y
x
c
s
v
ϕ
ϕ
ϕ
– znaki operandów s
ą identyczne (
0
)
(
)
(
1
1
=
−
−
−
k
k
y
x
ϕ
ϕ
),
•
k
k
c
s
=
−
)
(
1
ϕ
⇒ v = 0
– znaki operandów s
ą róŜne, a odjemna jest ujemna (
1
)
(
)
(
1
1
=
−
−
−
k
k
y
x
ϕ
ϕ
),
•
0
=
k
c
,
1
)
(
1
=
−
k
s
ϕ
⇒ v = 0
•
0
=
k
c
,
0
)
(
1
=
−
k
s
ϕ
⇒ v =
−
1
– znaki operandów s
ą róŜne, a odjemna jest dodatnia (
1
)
(
)
(
1
1
−
=
−
−
−
k
k
y
x
ϕ
ϕ
),
•
1
=
k
c
,
0
)
(
1
=
−
k
s
ϕ
⇒ v = 0
•
1
=
k
c
,
1
)
(
1
=
−
k
s
ϕ
⇒ v = 1
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–7
Inkrementacja i dekrementacja w systemach naturalnych
β
}
,
,...,
{
0
1
1
x
x
x
k
−
=
X
⇓ ⇓
1
+
±
=
±
i
i
i
i
c
s
c
x
β
⇓
1
0
±
=
c
β
}
,
,...,
{
0
1
1
s
s
s
k
−
=
±
1
X
})
1
,
0
{
}
1
,
0
{
(
}
1
,...,
1
,
0
{
,
1
∈
⇒
∈
⇒
−
∈
+
i
i
i
i
c
c
s
x
β
c
k
−2
x
1
s
1
c
2
s
k
−1
c
k
−1
c
k
x
k
−1
±
x
0
s
0
c
0
c
1
s
k
−2
x
k
−2
±
±
±
Schemat inkrementacji/dekrementacji
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–8
Zmiana znaku liczby w systemie uzupełnieniowym
W systemie pełnym
m
m
k
k
m
m
Y
Y
Y
−
−
−
−
−
−
+
−
−
+
+
+
−
=
+
−
−
=
−
β
β
β
β
β
β
β
β
]
)
1
)(
...
(
[
)
(
1
2
1
↓
m
k
m
i
i
i
k
k
k
m
i
i
k
y
y
Y
−
−
−
=
−
−
−
−
=
−
+
+
−
−
−
+
−
=
−
∑
∑
β
β
β
β
β
β
2
1
1
2
1
)
(
)
1
(
↓
ulp
Y
y
y
Y
m
k
m
i
i
i
k
k
+
=
+
+
−
=
−
−
−
−
=
−
−
∑
β
β
β
2
1
1
W ka
Ŝdym systemie uzupełnieniowym
)
(
Q
R
Y
Y
0
−
+
=
−
, czyli
)
(
]
)
1
[(
)
(
)
(
1
1
1
1
m
k
k
m
i
i
i
k
k
m
i
i
i
k
y
R
y
y
R
y
−
−
−
=
−
−
−
=
−
−
−
−
−
+
=
+
−
−
∑
∑
β
β
β
β
ϕ
β
ϕ
gdzie
m
k
R
−
−
=
δβ
β
oraz
δ
= 0 w systemie pełnym, 1 – w niepełnym,
a poniewa
Ŝ
)
(
1
)
(
1
1
−
−
−
=
k
k
y
y
ϕ
ϕ
m
k
m
i
i
i
k
y
R
y
Y
−
−
−
=
−
−
+
+
−
=
−
∑
β
δ
β
ϕ
)
1
(
)
(
1
1
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–9
Odejmowanie przez dodawanie
W systemie uzupełnieniowym
Y
X
Y
X
+
=
−
•
schemat uniwersalny, ale bardziej czasochłonny (dwukrotne dopełnianie)
albo, poniewa
Ŝ
)
(
Q
R
Y
Y
0
−
+
=
−
,
ulp
Y
X
Q
Y
X
Y
X
δ
+
+
==
+
+
=
−
~
•
dodawanie ulp – na najni
Ŝszej pozycji (zamiast przeniesienia c
–m
=0)
Odejmowanie liczb naturalnych przez dodanie uzupełnienia
β
β
U
1
1
1
1
}
,
,...,
,
0
{
}
,
,...,
{
m
m
k
m
m
k
x
x
x
x
x
x
−
+
−
−
−
+
−
−
=
m
m
m
k
m
m
k
y
y
y
y
y
y
−
−
+
−
−
−
+
−
−
+
−
=
−
δβ
β
β
β
U
1
1
1
1
}
,
,...,
,
1
{
}
,
,...,
{
Skoro
1
−
=
β
k
y
, x
k
= 0 i musi by
ć s
k
= 0, wi
ęc jeśli wynik jest poprawny, to
1
)]
(
)
(
[
]
)
(
[
1
1
−
=
+
−
+
=
+
+
k
k
k
k
k
c
y
x
c
s
v
ϕ
ϕ
ϕ
⇒ c
k+1
= 1 ⇒ c
k
= 1
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–10
Uniwersalny schemat dodawania i odejmowania
δ
= 1
c
k
−2
x
1–m
s
1–m
c
2–m
y
1–m
Σ
s
k
−1
c
k
−1
c
k
y
k
−1
x
k
−1
Σ
x
–m
s
–m
c
1–m
y
–m
Σ
s
k
−2
y
k
−2
x
k
−2
Σ
v
( )
( )
( )
( )
M
δ
= 0
y
M
k
−1
y
M
k
−2
y
M
1−
m
y
M
−
m
Schemat dodawania i odejmowania w systemach uzupełnieniowych
)]
(
)
(
[
]
)
(
[
1
1
1
M
k
k
k
k
y
x
c
s
v
−
−
−
+
−
+
=
ϕ
ϕ
ϕ
,
1
1
1
)
1
(
−
−
−
+
−
=
k
k
M
k
y
M
y
M
y
Liczby naturalne:
•
dodawanie – wynik poprawny gdy c
k
= 0
•
odejmowanie – wynik poprawny gdy c
k
= 1
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–11
Dodawanie i odejmowanie w naturalnym systemie dwójkowym
i
i
i
i
i
s
c
c
y
x
+
±
=
±
±
+
1
2
sumator pełny (full adder, FA) – realizuje funkcje
•
sumy arytmetycznej
i
s
operandów dwójkowych
i
i
i
c
y
x
,
,
na pozycji i-tej
•
przeniesienia
1
+
i
c
na wy
Ŝszą pozycję
i
i
i
i
c
y
x
s
⊕
⊕
=
,
i
i
i
i
i
i
i
i
i
i
i
c
y
x
y
x
c
y
x
y
x
c
)
(
)
(
1
+
+
=
⊕
+
=
+
subtraktor pełny (full subtracter, FS) – realizuje funkcje
•
ró
Ŝnicy arytmetycznej
i
s
operandów dwójkowych
i
i
i
c
y
x
,
,
na pozycji i-tej
•
po
Ŝyczki
1
+
i
c
z wy
Ŝszej pozycji
i
i
i
i
c
y
x
s
⊕
⊕
=
,
i
i
i
i
i
i
i
i
i
i
i
c
y
x
y
x
c
y
x
y
x
c
)
(
)
(
1
⊕
+
=
⊕
+
=
+
półsumator (half adder, HA) – realizuje funkcje
i
i
i
c
x
s
⊕
=
,
i
i
i
c
x
c
=
+
1
półsubtraktor (half subtracter, HS) – realizuje funkcje
i
i
i
c
x
s
⊕
=
,
i
i
i
c
x
c
=
+
1
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–12
Dodawanie i odejmowanie w dwójkowych systemach uzupełnieniowych
β
=2
⇒
1
1
)
(
−
−
=
k
k
x
x
ϕ
⇒
)
(
)
(
)
(
1
1
1
1
k
k
k
k
k
k
c
c
y
x
c
s
v
−
±
=
±
−
±
=
−
−
−
−
Mamy zatem (
m
k
R
−
−
=
2
2
δ
,
δ
=
0 w systemie U2 lub 1 w systemie U1)
m
k
k
k
k
m
i
i
i
k
c
R
c
c
s
R
s
S
−
−
−
−
=
−
±
−
±
+
−
=
∑
2
)
(
2
1
1
1
δ
Poprawny wynik mo
Ŝe być zawsze odtworzony w rozszerzeniu 1-pozycyjnym
•
w dodawaniu (liczb o jednakowych znakach)
v = 1 ⇒
1
1
−
−
=
k
k
c
s
⇒
}
,
,...,
,
{
1
1
e
m
m
k
k
s
s
s
c
−
+
−
−
=
S
•
w odejmowaniu (liczb o ró
Ŝnych znakach),
v = 1 ⇒
1
1
−
−
≠
k
k
c
s
⇒
}
,
,...,
,
{
1
1
1
e
m
m
k
k
s
s
s
c
−
+
−
−
−
=
S
W systemie uzupełnieniowym do 2 (U2)
k
k
k
k
m
i
i
i
k
k
c
c
s
s
S
2
)
(
2
2
1
2
1
1
−
±
+
−
=
−
−
−
=
−
−
∑
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–13
Zmiana znaku liczby w kodzie uzupełnieniowym
X
X
X
m
m
−
+
−
=
−
=
−
−
−
2
2
0
↓
m
m
m
k
k
m
m
X
X
X
−
−
+
−
−
−
−
−
+
−
+
+
+
−
=
+
−
−
=
−
2
]
)
2
2
...
2
(
2
[
2
)
2
(
1
2
1
↓
m
k
m
i
i
i
k
k
k
m
i
i
k
x
x
X
−
−
−
=
−
−
−
−
=
−
+
+
−
−
+
−
=
−
∑
∑
2
]
)
2
2
(
)
2
2
[(
2
1
1
2
1
↓
m
m
k
m
i
i
i
k
k
X
x
x
X
−
−
−
−
=
−
−
+
=
+
−
+
−
−
=
−
∑
2
2
]
2
)
1
(
2
)
1
(
[
2
1
1
↓
algorytmy mnemotechniczne: („1”=ulp=2
–m
– jednostka na najni
Ŝszej pozycji)
•
zaneguj wszystkie bity oryginału i do uzyskanego kodu dodaj pozycyjnie „1”
•
zaneguj wszystkie bity oryginału,
z wyj
ątkiem prawostronnego ciągu zer i poprzedzającej go „1”
(propagacja dodawanej „1” ko
ńczy się na pozycji najniŜszej „1” oryginału)
Dodawanie i odejmowanie
© Janusz Biernat, Dodawanie i odejmowanie, 14 pa
ździernika 2003
ADS–14
Dodawanie i odejmowanie liczb naturalnych jako rozszerze
ń w kodzie U2
U2
1
1
NB
1
1
}
,
,...,
,
0
{
}
,
,...,
{
m
m
k
m
m
k
x
x
x
x
x
x
−
+
−
−
−
+
−
−
=
↓
(s
k
=
c
k
),
ponadto w dodawaniu (c
k
+1
=
0
),
w odejmowaniu (c
k
+1
=
c
k
)
↓
k
k
k
m
i
i
i
k
m
i
i
i
i
k
c
s
y
x
S
2
2
2
)
(
2
)
0
0
(
1
1
±
=
±
+
±
−
=
∑
∑
−
−
=
−
−
=
Odejmowanie liczb naturalnych przez dodanie uzupełnienia
m
m
m
k
m
m
m
x
x
x
x
x
x
−
−
+
−
−
−
+
−
−
+
−
−
−
=
−
2
)}
1
(
),
1
(
),...,
1
(
,
1
{
}
,
,...,
{
U2
1
1
NB
1
1
↓
i
i
i
i
i
s
c
c
y
x
+
=
+
−
+
+
1
2
)
1
(
↓
k
k
k
m
i
i
i
m
k
m
i
i
i
i
k
c
s
y
x
S
2
)
1
(
2
2
2
))
1
(
(
2
)
1
0
(
1
1
−
−
=
+
−
+
+
+
−
=
∑
∑
−
−
=
−
−
−
=