unario meno e firmato da unsigned conversione

Question

È questo sempre tecnicamente corretta:

unsigned abs(int n) 
{ 
    if (n >= 0) { 
     return n; 
    } else { 
     return -n; 
    } 
} 

Mi sembra che qui se -INT_MIN> INT_MAX, l'espressione "-n" potrebbe traboccare quando n == INT_MIN , poiché -INT_MIN è fuori dai limiti. Ma sul mio compilatore sembra funzionare bene ... questo è un dettaglio di implementazione o un comportamento su cui si può fare affidamento?

versione più lunga

Un po 'di contesto: Sto scrivendo un wrapper C++ per il tipo intero GMP (mpz_t) e prendendo ispirazione per il C++ involucro esistente GMP (chiamato mpz_class). Quando si maneggia aggiunta di mpz_t con interi con segno c'è codice come questo:

static void eval(mpz_ptr z, signed long int l, mpz_srcptr w) 
{ 
    if (l >= 0) 
    mpz_add_ui(z, w, l); 
    else 
    mpz_sub_ui(z, w, -l); 
} 

In altre parole, se l'intero con segno è positivo, aggiungerlo utilizzando la routine di addizione senza segno, se l'intero con segno è negativo aggiungerlo usando la routine della sottrazione non firmata. Entrambe le routine * _ui prendono unsigned long come ultimi argomenti. Espressione

-l 

a rischio di traboccamento?

Answer 1

Se si desidera evitare l'overflow, è necessario prima eseguire il cast n su un int unsigned e quindi applicare lo meno unario a esso.

unsigned abs(int n) { 
    if (n >= 0) 
    return n; 
    return -((unsigned)n); 
} 

Nel codice originale la negazione avviene prima della conversione di tipo, quindi il comportamento è indefinito se n < -INT_MAX.

Quando si annulla un'espressione senza segno, non si verificherà mai un overflow. Il risultato sarà invece il modulo 2^x, per il valore appropriato di x.

Answer 2

Oggi la maggior parte dei computer utilizza una scala di numeri a due complementi, il che significa che la parte negativa è maggiore di quella positiva, ad esempio da -128 a 127. Ciò significa che se è possibile rappresentare il numero positivo il numero negativo è possibile rappresentare il numero negativo senza preoccupazione.

Answer 3

Sì, traboccherà, a se stesso.

#include <stdio.h> 
#include <limits.h> 
int main(int argc, char**argv) { 
    int foo = INT_MIN; 
    if (-foo == INT_MIN) printf("overflow\n"); 
    return 0; 
} 

stampe "troppo pieno"

Tuttavia, questo è un comportamento meramente tipico, non è richiesto dalla norma. Se vuoi giocare sul sicuro, vedi la risposta accettata per come.

Answer 4

forse potrebbe far fronte con la gamma simmetrica dei numeri 2's-complemento:

#include <limits.h> 

unsigned int abs(int n){ 

    unsigned int m; 

    if(n == INT_MIN) 
    m = INT_MAX + 1UL; 
    else if(n < 0) 
    m = -n; 
    else 
    m = n; 

    return m; 
} 

Answer 5

Molto buona domanda, che espone le differenze tra C89, C99 e C++. Quindi questo è un commento su questi standard.

In C89, dove n è un int:

(unsigned)n 

non è ben definito per ogni n: non c'è alcuna limitazione sulla conversione di int o senza segno eccetto che la rappresentazione di un int non negativo firmata è identico a quello di un int unsigned dello stesso valore, a condizione che il valore sia rappresentabile.

Questo è stato considerato un difetto, e in C99, purtroppo c'è un tentativo errato di limitare la codifica nel complemento a due, un complemento, o la grandezza firmato con lo stesso numero di bit. Sfortunatamente il comitato C non ha avuto molte conoscenze matematiche e ha completamente confuso le specifiche: da un lato è mal formato a causa di una definizione circolare e quindi non normativa, e d'altra parte, se si scusa questo errore, è una sovrascrittura lorda, che, ad esempio, esclude una rappresentazione BCD (utilizzata in C su mainframe IBM precedenti) e consente al programmatore di modificare il valore di un intero mediante bit di manipolazione della rappresentazione (che è molto cattivo).

C++ è andato a qualche problema per fornire una specifica migliore, tuttavia soffre dello stesso errore di definizione circolare.

In parole povere, la rappresentazione di un valore v è una matrice di caratteri senza segno con elementi sizeof (v). Un char senza segno ha una potenza di due numeri di elementi, ed è necessario che sia sufficientemente grande da garantire che codifichi fedelmente qualsiasi struttura di dati con alias. Il numero di bit in un char senza segno è ben definito come il registro binario del numero di valori rappresentabili.

Il numero di bit di qualsiasi valore senza segno è ugualmente ben definito se ha una potenza di due numeri di valori da 0 a 2^n-1, tramite lo schema di codifica di posizione canonica.

Purtroppo, il comitato ha voluto chiedere se ci fossero "buchi" nella rappresentazione. Ad esempio, potresti avere un intero 31 bit su una macchina x86? Dico sfortunatamente, perché questa è una domanda mal formata, e la risposta è ugualmente impropria.

Il modo corretto per fare questa domanda è chiedere se la rappresentazione è piena. Non è possibile parlare di "i bit di una rappresentazione" per interi con segno perché la specifica non passa dalla rappresentazione ai valori, ma va dall'altra parte. Ciò potrebbe confondere un sacco di programmatori che pensano erroneamente che una rappresentazione sia una mappatura da bit sottostanti ad un certo valore: una rappresentazione è una mappatura dai valori ai bit.

Una rappresentazione è piena se è una sorpresa, cioè è nell'intero intervallo dello spazio di rappresentazione. Se la rappresentazione è piena, non ci sono "buchi", cioè bit inutilizzati. Comunque non è tutto. Una rappresentazione di 255 valori su un array di 8 bit non può essere piena, ma non ci sono bit che non sono utilizzati. Non ci sono buchi

Il problema è questo: si consideri un int unsigned, quindi ci sono DUE rappresentazioni bitwise distinte. Esiste la matrice ben definita di log base 2 bit determinata dalla codifica canonica, e quindi c'è l'array di bit della rappresentazione fisica data dall'aliasing di una matrice di char senza segno. Anche se questa rappresentazione è piena, c'è nessuna corrispondenza tra i due tipi di bit.

Sappiamo tutti che i "bit di ordine elevato" della rappresentazione logica possono trovarsi a un'estremità della rappresentazione fisica su alcune macchine e l'altra su altre macchine: si chiama endianità.Ma in realtà non c'è ragione per cui i bit non possano essere permutati in nessun ordine, infatti non c'è motivo per cui i bit debbano essere allineati! Basti pensare di aggiungere 1 modulo al valore massimo più 1 come rappresentazione per vederlo.

Quindi ora il problema è che per gli interi con segno c'è no rappresentazione logica canonica, piuttosto ce ne sono molti comuni: il complemento a due, per esempio. Tuttavia come sopra questo è non correlato alla rappresentazione fisica. Il comitato C non ha potuto capire che la corrispondenza tra i valori e la rappresentazione fisica non può essere specificata parlando dei bit. È necessario specificare interamente parlando delle proprietà delle funzioni.

Poiché ciò non è stato fatto, lo standard C99 contiene termini non normativi e di conseguenza tutte le regole per il comportamento delle conversioni di interi con segno e senza segno sono anch'esse non-normative.

Pertanto non è chiaro che

(unsigned)n 

sarà effettivamente produrre il risultato desiderato per i valori negativi.

Answer 6

Non esiste un overflow di numeri interi senza segno in C. L'aritmetica per loro è chiaramente definita come modulo di computazione il loro max + 1, essi possono "avvolgere" ma tecnicamente questo non è considerato overflow. Quindi la parte di conversione del tuo codice va bene, anche se in casi estremi potresti riscontrare risultati sorprendenti.

L'unico punto in cui è possibile avere un overflow nel codice è lo - di un tipo firmato. Esiste esattamente un valore per i tipi firmati che potrebbero non avere una contropartita positiva, il valore minimo. In realtà per quello che avrebbe dovuto fare un controllo speciale, ad esempio per int

if (INT_MIN < -INT_MAX && n == INT_MIN) /*do something special*/ 

Answer 7

Questo dovrebbe evitare comportamenti indefiniti e lavorare con tutte le rappresentazioni di int firmato (complemento a 2, 1 complemento, segno e grandezza):

unsigned myabs(int v) 
{ 
    return (v >= 0) ? (unsigned)v : (unsigned)-(v+1)+1; 
} 

compilatori moderni sono in grado di rimuovere la ridondanza -1+1 e riconoscere il linguaggio per calcolare il valore assoluto di un numero intero con segno.

Ecco cosa gcc produce:

_myabs: 
    movl 4(%esp), %eax 
    cltd 
    xorl %edx, %eax 
    subl %edx, %eax 
    ret