Non riesco a capire perché i sistemi a microprocessore implementino numeri senza segno. Immagino che il costo sia solo il doppio del numero di rami condizionali, poiché maggiore di, minore di, .etc, necessita di un algoritmo diverso da quello firmato, esistono ancora algoritmi per i quali i numeri senza segno rappresentano un vantaggio significativo per?
la mia domanda è in parte il motivo per cui devono essere nel set di istruzioni come contrario a essere supportato da un compilatore?
I numeri senza segno sono un'interpretazione di una sequenza di bit. È anche l'interpretazione più semplice e più utilizzata internamente alla CPU perché gli indirizzi e i codici operativi sono semplicemente bit. L'indirizzamento e l'aritmetica di memoria / pila sono le basi del microprocessore, bene, dell'elaborazione. Spostando la piramide di astrazione, un'altra frequente interpretazione dei bit è come un carattere (ASCII, Unicode, EBCDIC). Poi ci sono altre interpretazioni come IEEE Floating point, RGBA per la grafica e così via. Nessuno di questi è un semplice numero firmato (IEEE FP non è semplice, e l'aritmetica che usa quelli è molto complicata).
Inoltre, con aritmetica non firmata è piuttosto semplice (se non più efficiente) implementare gli altri. Il contrario non è vero.
La maggior parte del costo dell'hardware per le operazioni di confronto è la sottrazione. L'output della sottrazione utilizzata dal confronto è essenzialmente tre bit di stato:
Con la corretta combinazione di testare questi tre bit dopo l'operazione di sottrazione, possiamo determinare tutte le operazioni relazionali firmate, così come tutte le operazioni relazionali senza segno (questi bit sono anche il modo in cui viene rilevato l'overflow, firmato e non firmato). Lo stesso hardware ALU di base può essere condiviso per implementare tutti questi confronti (per non parlare dell'istruzione di sottrazione), fino al controllo finale di quei tre bit di stato, che differiscono secondo il confronto relazionale desiderato. Quindi, non è un sacco di hardware extra.
L'unico costo reale è la necessità della codifica di ulteriori modalità di confronto nell'architettura dell'insieme di istruzioni, che può ridurre marginalmente la densità delle istruzioni. Tuttavia, è abbastanza normale che l'hardware abbia molte istruzioni che non sono usate da nessuna lingua specifica.
Perché, se hai bisogno di contare qualcosa che è sempre >= 0 , ridurrai inutilmente lo spazio di conteggio a metà usando interi con segno.
Considera il PK INT auto-incrementato che potresti mettere sulle tue tabelle del database. Se utilizzi un numero intero con segno, la tua tabella memorizza HALF quanti più record potrebbe per la stessa dimensione del campo senza alcun vantaggio.
O gli ottetti di un colore RGBa. Non vogliamo iniziare maldestramente a contare questo concetto di numero naturalmente positivo con un numero negativo. Un numero firmato potrebbe rompere il modello mentale o dimezzare il nostro spazio. Un intero senza segno non solo corrisponde al concetto, ma fornisce il doppio della risoluzione.
Dal punto di vista dell'hardware, gli interi senza segno sono semplici. Sono probabilmente la struttura bit più semplice per eseguire calcoli matematici. E, senza dubbio, potremmo semplificare l'hardware simulando i tipi di interi (o anche i virgola mobile!) In un compilatore. Quindi, perché entrambi gli interi con segno e non firmati implementati in hardware?
Bene ... prestazioni!
È più efficiente implementare interi con segno nell'hardware che nel software. L'hardware può essere istruito per eseguire calcoli matematici su entrambi i tipi di numero intero in una singola istruzione. E questo è molto buono , perché l'hardware distrugge i bit più o meno in parallelo. Se provi a simularlo nel software, il tipo intero che scegli di "simulare" richiederà indubbiamente molte istruzioni e notevolmente più lento.
La tua domanda consiste di due parti:
Qual è lo scopo degli interi senza segno?
Gli interi senza segno vale il problema?
I numeri senza segno, molto semplicemente, rappresentano una classe di quantità per cui i valori negativi sono privi di significato. Certo, potresti dire che la risposta alla domanda "quante mele ho?" potrebbe essere un numero negativo se devi delle mele a qualcuno, ma per quanto riguarda la domanda di "quanta memoria ho?" - Non puoi avere una quantità di memoria negativa. Pertanto, gli interi senza segno sono molto adatti a rappresentare tali quantità e hanno il vantaggio di essere in grado di rappresentare il doppio del range di valori positivi rispetto a quelli con segno. Ad esempio, il valore massimo che puoi rappresentare con un numero intero con segno a 16 bit è 32767, mentre con un numero intero senza segno a 16 bit è 65535.
Gli interi senza segno non rappresentano alcun problema, quindi, sì, ne vale la pena. Vedete, non richiedono un set extra di "algoritmi"; il circuito richiesto per implementarli è un sottoinsieme del circuito richiesto per implementare interi con segno.
Una CPU non ha un moltiplicatore per interi con segno e un moltiplicatore diverso per quelli senza segno; ha solo un moltiplicatore, che funziona in modo leggermente diverso a seconda della natura dell'operazione. Il supporto della moltiplicazione firmata richiede un circuito un po 'più corto di quello non firmato, ma dal momento che deve essere comunque supportato, la moltiplicazione non firmata è praticamente gratuita, è inclusa nel pacchetto.
Per quanto riguarda l'addizione e la sottrazione, non vi è alcuna differenza nel circuito. Se leggi la cosiddetta rappresentazione a complemento a due di interi scoprirai che è progettata in modo così intelligente che queste operazioni possono essere eseguite esattamente allo stesso modo, indipendentemente dalla natura degli interi.
Il confronto funziona allo stesso modo, poiché non è altro che sottrarre-e-scartare-il-risultato, l'unica differenza è nelle istruzioni del ramo condizionale (salto), che funzionano osservando i diversi flag della CPU che sono impostato dall'istruzione precedente (confronto). In questa risposta: link puoi trovare una spiegazione di come funzionano sull'architettura Intel x86. Quello che succede è che la designazione di un'istruzione di salto condizionale come firmata o non firmata dipende da quali flag esamina.
I microprocessori sono intrinsecamente non firmati. I numeri firmati sono la cosa che viene implementata, non il contrario.
I computer possono funzionare bene senza numeri firmati, ma noi, gli umani che hanno bisogno di numeri negativi, è stata inventata la firma.
Perché hanno un altro bit che è facilmente disponibile per l'archiviazione e non ti devi preoccupare dei numeri negativi. Non c'è molto di più.
Ora se hai bisogno di un esempio di dove hai bisogno di questo bit in più, ce ne sono molte da trovare se guardi.
Il mio esempio preferito viene dai bitboard nei motori di Chess. Ci sono 64 quadrati su una scacchiera, quindi un unsigned long fornisce una perfetta conservazione per una varietà di algoritmi che ruotano attorno alla generazione del movimento. Considerando il fatto che è necessario eseguire operazioni binarie (così come le operazioni di spostamento !!), è facile capire perché è più semplice non doversi preoccupare di quali cose speciali accadono se l'MSB è impostato. Può essere eseguito con firma lunga, ma è un lotto più facile da usare senza segno.
Avere uno sfondo di matematica pura, questa è una presa leggermente più matematica per chiunque sia interessato.
Se iniziamo con un intero con segno e senza segno a 8 bit, ciò che abbiamo è fondamentalmente l'intero modulo 256, per quanto riguarda l'addizione e la moltiplicazione, a patto che il complemento a 2 sia usato per rappresentare interi negativi (ed è così che ogni processore moderno lo fa).
Dove le cose differiscono si trova in due punti: uno è operazioni di confronto. In un certo senso, gli interi modulo 256 sono meglio considerati una cerchia di numeri (come gli interi modulo 12 do su un quadrante analogico vecchio stile). Per rendere significativi i confronti numerici (è x < y), dovevamo decidere quali numeri sono meno di altri. Dal punto di vista del matematico, vogliamo incorporare gli interi modulo 256 nell'insieme di tutti gli interi in qualche modo. Mappare il numero intero a 8 bit la cui rappresentazione binaria è tutti zero per l'intero 0 è la cosa ovvia da fare. Possiamo quindi procedere alla mappatura degli altri in modo che '0 + 1' (il risultato dell'azzeramento di un registro, diciamo ax e dell'incremento di uno, tramite 'inc ax') vada al numero intero 1, e così via. Possiamo fare lo stesso con -1, ad esempio mappando '0-1' al numero intero -1, e '0-1-1' all'intero -2. Dobbiamo assicurarci che questa incorporazione sia una funzione, quindi non possiamo mappare un singolo intero da 8 bit a due interi. Come tale, questo significa che se mappiamo tutti i numeri nel set di numeri interi, ci sarà 0, insieme ad alcuni numeri interi minori di 0 e alcuni più di 0. Ci sono essenzialmente 255 modi per farlo con un intero a 8 bit (secondo a quale minimo si desidera, da 0 a -255). Quindi puoi definire 'x < in termini di '0 < y - x '.
Ci sono due casi d'uso comuni, per i quali il supporto hardware è ragionevole: uno con tutti i numeri interi diversi da zero e uno con uno spacco approssimativamente 50/50 attorno a 0. Tutte le altre possibilità sono facilmente emulate traducendo i numeri tramite un extra 'add e sub' prima delle operazioni, e la necessità di questo è così rara che non riesco a pensare ad un esempio esplicito nel software moderno (dal momento che puoi semplicemente lavorare con una mantissa più grande, diciamo 16 bit).
L'altro problema è quello di mappare un intero a 8 bit nello spazio degli interi a 16 bit. -1 va a -1? Questo è ciò che vuoi se 0xFF è pensato per rappresentare -1. In questo caso, estendere il segno è la cosa giusta da fare, in modo che 0xFF vada a 0xFFFF. D'altra parte, se 0xFF era pensato per rappresentare 255, allora lo si vuole mappare a 255, quindi a 0x00FF, piuttosto che a 0xFFFF.
Questa è la differenza tra le operazioni "shift" e "arithmetic shift".
In definitiva, tuttavia, si riduce al fatto che i file int nel software non sono interi, ma rappresentazioni in binario, e solo alcuni possono essere rappresentati. Quando si progetta l'hardware, è necessario fare delle scelte su cosa fare in modo nativo nell'hardware. Poiché con il complemento a 2 le operazioni di addizione e moltiplicazione sono identiche, ha senso rappresentare gli interi negativi in questo modo. Quindi è solo una questione di operazioni che dipendono da quali numeri interi le rappresentazioni binarie intendono rappresentare.
Consente di esaminare il costo di implementazione per l'aggiunta di interi non firmati a un progetto CPU con interi con segno esistente.
Una tipica CPU ha bisogno delle seguenti istruzioni aritmetiche:
Ha anche bisogno di istruzioni logiche:
Per eseguire i suddetti rami su confronti di interi con segno, il modo più semplice è che l'istruzione SUB abbia i seguenti flag:
Quindi i rami aritmetici sono implementati come segue:
Le negazioni di queste dovrebbero seguire ovviamente da come vengono implementate.
Quindi il tuo design esistente implementa già tutti questi elementi per interi con segno. Ora consideriamo cosa dobbiamo fare per aggiungere interi senza segno:
Si noti che in ogni caso, le modifiche sono molto semplici e possono essere implementate semplicemente attivando o disattivando una piccola sezione di circuiti o aggiungendo un nuovo registro flag che può essere controllato da un valore che deve essere calcolato come parte dell'implementazione delle istruzioni comunque.
Pertanto, il costo dell'aggiunta di istruzioni non firmate è molto piccolo . Per quanto riguarda il motivo per cui dovrebbe essere fatto , si noti che gli indirizzi di memoria (e gli offset negli array) sono valori intrinsecamente non firmati. Poiché i programmi impiegano molto tempo a manipolare gli indirizzi di memoria, avere un tipo che li gestisca correttamente rende i programmi più facili da scrivere.
I numeri senza segno esistono in gran parte per gestire situazioni in cui è necessario un anello algebrico di tipo wrapping (per un tipo senza segno a 16 bit, sarebbe l'anello di interi congruente mod 65536). Prendi un valore, aggiungi qualsiasi importo inferiore al modulo e la differenza tra i due valori sarà la somma che è stata aggiunta. Come esempio reale, se un contatore di utilità legge 9995 all'inizio di un mese e uno utilizza 23 unità, il contatore leggerà 0018 alla fine del mese. Quando si utilizza un tipo di anello algebrico, non è necessario fare qualcosa di speciale per gestire l'overflow. Sottraendo 9995 da 0018 si otterrà 0023, precisamente il numero di unità che sono state utilizzate.
Sul PDP-11, la macchina per la quale C è stata implementata per la prima volta, c'erano nessun tipo di numero intero senza segno, ma i tipi firmati potrebbero essere utilizzati per modulare aritmetica che si è conclusa tra 32767 e -32768 anziché in mezzo 65535 e 0. Le istruzioni dei numeri interi su alcune altre piattaforme no avvolgere le cose in modo pulito, comunque; piuttosto che richiedere tali implementazioni deve emulare i numeri interi a due complementi usati nel PDP-11, la lingua invece ha aggiunto i tipi senza segno che principalmente dovevano comportarsi come algebrici squilla e consente ai tipi di interi con segno di comportarsi in altri modi in caso di trabocco.
Nei primi giorni di C, c'erano molte quantità che potevano superare 32767 (il comune INT_MAX) ma non 65535 (il comune UINT_MAX). esso così divenne comune usare tipi non firmati per contenere tali quantità (ad es. size_t). Sfortunatamente, non c'è niente nella lingua da distinguere tra i tipi che dovrebbero comportarsi come numeri con un tocco in più gamma positiva, contro tipi che dovrebbero comportarsi come anelli algebrici. Invece, il linguaggio rende i tipi più piccoli di "int" si comportano come numeri mentre i tipi a grandezza naturale si comportano come anelli algebrici. Di conseguenza, chiamare funzione come:
uint32_t mul(uint16_t a, uint16_t b) { return a*b; }
con (65535, 65535) avrà un comportamento definito su sistemi in cui int è 16 bit (ovvero return 1), un comportamento diverso dove int è 33 bit o più grande (restituisce 0xFFFE0001) e comportamento non definito su sistemi in cui "int" è ovunque nel mezzo [nota che gcc di solito produce risultati aritmetici corretti con i risultati tra INT_MAX + 1u e UINT_MAX, ma a volte genererà il codice per la funzione precedente che fallisce con tale valori!]. Non molto utile.
Tuttavia, la mancanza di tipi che si comportano in modo consistente come numeri o consistentemente come un anello algebrico non cambia il fatto che i tipi di anello algebrico sono quasi indispensabili per alcuni tipi di programmazione.
Leggi altre domande sui tag numbers