Numeri negativi in binario
Finora abbiamo parlato di numeri interi positivi e di come vengono rappresentati nei nostri computer. Tuttavia, a volte c’è bisogno di lavorare anche con numeri negativi. In che modo i computer li rappresentano?
Abbiamo visto che il numero 1 è rappresentato come
0001 in binario, il numero 6 è rappresentato come 0110 e così via. Lo 0 viene rappresentato come tutti zeri 0000. Un trucco logico per memorizzare i numeri negativi consiste nel mantenere un bit “speciale” che indichi se il numero è negativo. Se questo bit è 1, il numero è negativo; se è 0, il numero è positivo. Ed è esattamente così che la maggior parte dei computer gestisce i numeri negativi: mettono un bit speciale completamente a sinistra della rappresentazione binaria, impostato a 1 se il numero è negativo e a 0 se è positivo.C’è però qualcosa in più rispetto all’avere solo 1 come primo bit nella rappresentazione. Nella rappresentazione decimale (i nostri numeri abituali come 4, 5, 10, 311, ecc.) i numeri negativi e positivi si compensano a vicenda. Per esempio, 6 più -6 dà come risultato 0. Questa proprietà non dovrebbe andare persa nemmeno in binario. Quindi, se in binario sommiamo 6 e -6, dovremmo ottenere 0.
Immaginiamo di avere 4 bit per rappresentare il numero e 1 bit per il segno, per un totale di 5 bit. Di conseguenza, 6 sarà rappresentato come
00110, mentre 0 sarà 00000. La rappresentazione binaria di -6 deve essere l’opposto di quella di 6, in modo che la loro somma dia 0. Anticipando un po’, la rappresentazione di -6 è 11010. Di conseguenza, se aggiungiamo 00110 e 11010 in binario, otterremo 00000.Per passare da un numero positivo a uno negativo (e viceversa) in binario, possiamo usare un trucco semplice: invertire tutti i bit (trasformare tutti gli 0 in 1 e tutti gli 1 in 0) e poi aggiungere 1 al risultato.
x = 6 # 00110
x = ~x + 1 # Inverti tutti i bit e aggiungi 1 => -6
x = ~x + 1 # Inverti tutti i bit e aggiungi 1 => 6
z = 0 # 00000
z = ~z + 1 # Inverti e aggiungi 1 => 0
z = ~z + 1 # Inverti e aggiungi 1 => 0
z = ~z # -1 (tutti 1 nella rappresentazione binaria)
z = ~z # 0 (tutti 0 nella rappresentazione binaria)Ricorda che l’addizione in binario si effettua allo stesso modo dell’addizione in decimale, partendo dalla cifra meno significativa verso quella più significativa (considerando il riporto).
A seconda del linguaggio e dell’implementazione, i computer memorizzano i numeri in modo diverso. Linguaggi come C++ e Java hanno tipi distinti per valori di diversa ampiezza. Il tipo
int memorizza gli interi in 32 bit: 31 bit per il numero e il bit iniziale per il segno ⇒ i numeri possono variare da -2,147,483,648 () a 2,147,483,647 (). Nota che i positivi arrivano fino a uno in meno rispetto ai negativi. Ciò accade perché i numeri positivi iniziano con un bit a 0 e il primo valore che inizia con un bit a 0 è lo 0 stesso (tutti 0).Sfida
Nella terra magica del 7, tutto è progettato per avere un legame con il numero 7. In questo regno, gli scienziati informatici hanno sviluppato un sistema in cui i numeri binari (sia positivi che negativi) vengono memorizzati in 77 bit.
Data una stringa di bit
b, il tuo compito è calcolare il valore negativo di quel numero e rappresentarlo in 77 bit.Input
L’input contiene una singola riga che rappresenta la stringa di bit
b (1 ≤ |b| ≤ 77). Può rappresentare un numero sia positivo che negativo.Output
L’output deve contenere una singola riga che rappresenta
-b, con lunghezza 77.Esempi
Ingresso | Uscita |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB