Rappresentazione in modulo e segno
La prima notazione possibile consiste nell'utilizzare il primo bit del numero (quello più a sinistra) per indicare il segno del numero:
Contro: esiste un +0 e un -0.
Esempio: -14
Escludo temporaneamente il segno e converto:
14:2=7 R=0 0
7:2=3 R=1 1
3:2=1 R=1 2
1:2=0 R=1 3
Ora estendo il numero su 8 bit e cambio quello più significativo e ottengo:
10001110
Rappresentazione in complemento a 1 (in base 2)
La seconda notazione possibile consiste nel complementare l'intero numero. Come prima, il primo bit diventa 1, ma ne cambiano anche altri.
Il complemento a 1 del complemento a 1 di un numero N è proprio N.
Contro: la somma di un due numeri opposti non dà 0.
Esempio: -14
Escludo temporaneamente il segno e converto:
14:2=7 R=0 0
7:2=3 R=1 1
3:2=1 R=1 2
1:2=0 R=1 3
Ora estendo il numero su 8 bit, ne eseguo il NOT e ottengo:
11110001
Rappresentazione in complemento a 2 (in base 2)
La terza notazione possibile consiste nel aggiungere 1 al complemento a 1. In questo modo la somma di un numero e del suo opposto è 0.
Inoltre il complemento a 2 (in base 2) del complemento a 2 (in base 2) di un numero N è proprio N.
Esempio: -14
Escludo temporaneamente il segno e converto:
14:2=7 R=0 0
7:2=3 R=1 1
3:2=1 R=1 2
1:2=0 R=1 3
Ora estendo il numero su 8 bit, ne eseguo il NOT, sommo 1 e ottengo:
11110010
Infatti, sommando 00001110+11110010 si ottiene 100000000.
Tale risultato, troncato ad 8 bit (da destra), ovvero a modulo 256 (\( 2^8=256 \)), è proprio lo zero che desideravamo.
Per capire meglio...
Complemento in base \( b \) a \( n \) cifre (di un numero x)
Il complemento in base \( b \) a \( n \) cifre di un numero \( x \), con \( 0 \le x < b^n \), è definito come:
\[ C_b^n(x) = b^n - x \]
Equivalentemente, in aritmetica modulare:
\[ C_b^n(x) ≡ -x \mod b^n \]
Proprietà:
Il complemento in base \( b \) del complemento in base \( b \) di un numero x è proprio x.
\[ C_b^n(C_b^n(x)) = x \]
Complemento in base b=10 (di un numero x)
Esempio: se siamo in base 10 (quindi b = 10) e vogliamo il complemento in base b=10 a 3 cifre del numero 245:
\[ C_{10}^3(245) = 10^3 - 245 = 1000 - 245 = 755 \]
Quindi 755 è il complemento in base 10 a 3 cifre di 245.
Complemento in base b=2 (di un numero x)
Esempio: se siamo in base 2 (quindi b = 2) e vogliamo il complemento in base b=2 a 4 cifre del numero 1011:
\[ C_{2}^4(1011) = 2^4 - 1011_2 = 10000_2 - 1011_2 = 0101_2 \]
Quindi 0101 è il complemento in base 2 a 4 cifre di 1011.
A cosa serve il complemento
Serve soprattutto per fare le sottrazioni usando solo addizioni, cosa molto utile nei computer e nei circuiti digitali, che eseguono calcoli \( \mod 2^{8} \), \( \mod 2^{16} \), \( \mod 2^{32} \), \( \mod 2^{64} \) a seconda del numero di bit del microprocessore.
Quindi sempre con \( 0 \le y < b^n \):
\[ x - y = x + C_b^n(y) - b^n \]
\[ (x-y) \mod b^n ≡ (x + C_b^n(y)) \mod b^n \]
Supponiamo di dover effettuare, in base 10, il calcolo 193 - 245. Abbiamo due alternative:
- Uso aritmetica classica (e un poco di algebra):
\[ z = x - y = -(y-x) \]
Esempio (in base 10):
\[
\begin{align*}
193 - 245 &= - (245 - 193) \\
&= -52
\end{align*}
\]
- Uso aritmetica modulare:
\[ x - y = x + C_b^n(y) - b^n \]
Esempio (in base 10):
\[
\begin{align*}
193 - 245 \\
&= 193 + C_{10}^3(245) - 10^3 \\
&= 193 + 755 - {10}^3 \\
&= 942 - {10}^3 \\
&= -52
\end{align*}
\]
Esempio (in base 10):
\[
\begin{align*}
(193-245) \mod {10}^3 \\
&≡ (193 + C_{10}^3(245)) \mod {10}^3 \\
&≡ (193 + 755) \mod {10}^3 \\
&≡ 942 \mod {10}^3 \\
&≡ -52 \mod {10}^3
\end{align*}
\]
Complemento in base b=2 (di un numero x)
Supponiamo di dover effettuare, in base 2, il calcolo 25 - 45.
\[ C_2^8(45) = 2_{10}^8 - 45_{10} = 211_{10} \]
\[ C_2^8(45) = 100000000_2 - 00101101_2 = 11010011_2 \]
Esempio (in base 2):
\[
\begin{align*}
25_{10} - 45_{10} \\
&= 25_{10} + C_2^8(45) - 2^8 \\
&= 00011001_2 + 11010011_2 - 100000000_2 \\
&= 11101100_2 \\
&= 236_{10} \\
&= -20_{10}
\end{align*}
\]
Esempio (in base 2):
\[
\begin{align*}
(25_{10} - 45_{10}) \mod 2^8 \\
&≡ (25_{10} + C_2^8(45)) \mod 2^8 \\
&≡ (00011001_2 + 11010011_2) \mod 2^8 \\
&≡ 11101100_2 \mod 2^8 \\
&≡ 236_{10} \mod 2^8 \\
&≡ -20_{10} \mod 2^8
\end{align*}
\]
Complemento diminuito in base \( b \) a \( n \) cifre (di un numero x)
Il complemento diminuito (o complemento alla base-1) in base \( b \) a \( n \) cifre di un numero \( x \), con \( 0 \le x < b^n \), è definito come:
\[ R_b^n(x) = b^n - 1 - x \]
Proprietà:
Il complemento diminuito in base \( b \) si può anche calcolare eseguendo, per ogni cifra \( x_i \) del numero \( x \), l'operazione:
\[ x_i^c = b - 1 - x_i \]
Proprietà:
Il complemento (diminuito) in base \( b \) del complemento (diminuito) in base \( b \) di un numero x è proprio x.
\[ R_b^n(R_b^n(x)) = x \]
Proprietà:
Dalla definizione, segue immediatamente che:
\[ C_b^n(x) = R_b^n(x)+1 \]
Attenzione:
la definizione di "complemento a 1" è quindi da intendersi come "complemento diminuito in base 2", ovvero come "complemento a 1 in base 2", e non certo come "complemento in base 1".
Per quanto riguarda la base 10, si parla di complemento (diminuito) in base 10, oppure di complemento a 9 in base 10.