Gli operatori di spostamento (<<, >>) sono aritmetici o logici in C?

https://stackoverflow.com/questions/7622

08-06-2019
|

Domanda

In C, sono gli operatori di spostamento (<<, >>) aritmetico o logico?

Soluzione

Secondo K&R 2a edizione i risultati dipendono dall'implementazione per gli spostamenti a destra dei valori con segno.

Wikipedia dice che C/C++ "solitamente" implementa uno spostamento aritmetico sui valori con segno.

Fondamentalmente devi testare il tuo compilatore o non fare affidamento su di esso.Il mio aiuto VS2008 per l'attuale compilatore MS C++ dice che il loro compilatore esegue uno spostamento aritmetico.

Altri suggerimenti

Quando si sposta a sinistra, non c'è differenza tra spostamento aritmetico e logico.Quando si sposta a destra, il tipo di spostamento dipende dal tipo di valore da spostare.

(Come sfondo per quei lettori che non hanno familiarità con la differenza, uno spostamento "logico" a destra di 1 bit sposta tutti i bit a destra e riempie il bit più a sinistra con uno 0.Uno spostamento "aritmetico" lascia il valore originale nel bit più a sinistra.La differenza diventa importante quando si ha a che fare con numeri negativi.)

Quando si sposta un valore senza segno, l'operatore >> in C è uno spostamento logico.Quando si sposta un valore con segno, l'operatore >> è uno spostamento aritmetico.

Ad esempio, supponendo una macchina a 32 bit:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

TL;DR

Prendere in considerazione i E n essere rispettivamente gli operandi sinistro e destro di un operatore di spostamento;il tipo di i, dopo la promozione a numeri interi, be T.Supponendo n essere in [0, sizeof(i) * CHAR_BIT) - altrimenti non definito - abbiamo questi casi:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

^{† la maggior parte dei compilatori lo implementa come spostamento aritmetico}
^{‡ indefinito se il valore supera il risultato tipo T;tipo promosso di i}

Mutevole

Il primo è la differenza tra spostamenti logici e aritmetici da un punto di vista matematico, senza preoccuparsi della dimensione del tipo di dati.Gli spostamenti logici riempiono sempre i bit scartati con zeri mentre lo spostamento aritmetico li riempie di zeri solo per lo spostamento a sinistra, ma per lo spostamento a destra copia l'MSB preservando così il segno dell'operando (assumendo un complemento a due codifica per valori negativi).

In altre parole, lo spostamento logico considera l'operando spostato come un semplice flusso di bit e li sposta, senza preoccuparsi del segno del valore risultante.Lo spostamento aritmetico lo considera un numero (con segno) e preserva il segno mentre vengono effettuati gli spostamenti.

Uno spostamento aritmetico a sinistra di un numero X per n equivale a moltiplicare X per 2^N ed è quindi equivalente allo spostamento logico a sinistra;anche uno spostamento logico darebbe lo stesso risultato poiché MSB cade comunque dalla fine e non c'è nulla da preservare.

Uno spostamento aritmetico a destra di un numero X per n equivale alla divisione intera di X per 2^N SOLO se X è non negativo!La divisione intera non è altro che una divisione matematica e girare verso 0 (tronco).

Per i numeri negativi, rappresentati dalla codifica in complemento a due, lo spostamento verso destra di n bit ha l'effetto di dividerlo matematicamente per 2^N e arrotondando verso −∞ (pavimento);quindi lo spostamento a destra è diverso per valori non negativi e negativi.

per X ≥ 0, X >> n = X / 2^N = tronca(X ÷ 2^N)

per X < 0, X >> n = pavimento(X ÷ 2^N)

Dove ÷ è la divisione matematica, / è la divisione intera.Diamo un'occhiata ad un esempio:

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37/2 = 18 (arrotondando 18,5 allo 0) = 10010)₂ [risultato dello spostamento aritmetico a destra]

-37)₁₀ = 11011011)₂ (considerando un complemento a due, rappresentazione a 8 bit)

-37 ÷ 2 = -18.5

-37/2 = -18 (arrotondamento 18,5 allo 0) = 11101110)₂ [NON il risultato dello spostamento aritmetico a destra]

-37 >> 1 = -19 (arrotondamento 18,5 verso −∞) = 11101101)₂ [risultato dello spostamento aritmetico a destra]

COME Guy Steele ha sottolineato, questa discrepanza ha portato a bug in più di un compilatore.Qui non negativo (matematica) può essere mappato su valori non negativi senza segno e con segno (C);entrambi vengono trattati allo stesso modo e lo spostamento a destra viene eseguito mediante divisione intera.

Quindi logico e aritmetico sono equivalenti nello spostamento a sinistra e per valori non negativi nello spostamento a destra;è nel giusto spostamento dei valori negativi che differiscono.

Tipi di operandi e risultati

Norma C99 §6.5.7:

Ciascuno degli operandi deve avere tipi interi.

Le promozioni di numeri interi vengono eseguite su ciascuno degli operandi.Il tipo del risultato è quello dell'operando sinistro promosso.Se il valore dell'operando di destra è negativo o è maggiore o uguale alla larghezza dell'operando di sinistra promosso, il comportamento non è definito.

short E1 = 1, E2 = 3;
int R = E1 << E2;

Nello snippet precedente, entrambi gli operandi diventano int (a causa della promozione dei numeri interi);Se E2 era negativo o E2 ≥ sizeof(int) * CHAR_BIT allora l'operazione non è definita.Questo perché lo spostamento di più bit rispetto a quelli disponibili causerà sicuramente un overflow.Avevo R stato dichiarato come short, IL int il risultato dell'operazione di spostamento verrebbe implicitamente convertito in short;una conversione restrittiva, che può portare a un comportamento definito dall'implementazione se il valore non è rappresentabile nel tipo di destinazione.

Tasto maiuscolo di sinistra

Il risultato di E1 << E2 è la posizione dei bit E2 spostata a sinistra E1;i bit lasciati liberi vengono riempiti con zeri.Se E1 ha un tipo senza segno, il valore del risultato è E1×2^E2, ridotto modulo uno in più rispetto al valore massimo rappresentabile nel tipo risultato.Se E1 ha un tipo con segno e un valore non negativo e E1×2^E2 è rappresentabile nel tipo di risultato, questo è il valore risultante;in caso contrario, il comportamento non è definito.

Poiché gli spostamenti a sinistra sono gli stessi per entrambi, i bit lasciati liberi vengono semplicemente riempiti con zeri.Quindi afferma che sia per i tipi senza segno che per quelli con segno si tratta di uno spostamento aritmetico.Lo interpreto come uno spostamento aritmetico poiché gli spostamenti logici non si preoccupano del valore rappresentato dai bit, lo considerano semplicemente come un flusso di bit;ma lo standard parla non in termini di bit, ma definendolo in termini di valore ottenuto dal prodotto di E1 con 2^E2.

L'avvertenza qui è che per i tipi con segno il valore dovrebbe essere non negativo e il valore risultante dovrebbe essere rappresentabile nel tipo di risultato.Altrimenti l'operazione non è definita. Il tipo di risultato sarebbe il tipo di E1 dopo aver applicato la promozione integrale e non il tipo di destinazione (la variabile che manterrà il risultato).Il valore risultante viene convertito implicitamente nel tipo di destinazione;se non è rappresentabile in quel tipo, allora la conversione è definita dall'implementazione (C99 §6.3.1.3/3).

Se E1 è un tipo con segno con un valore negativo, il comportamento dello spostamento a sinistra non è definito. Questa è una strada facile verso un comportamento indefinito che può facilmente essere trascurato.

Spostamento a destra

Il risultato di E1 >> E2 è la posizione dei bit E2 spostata a destra di E1.Se E1 ha un tipo senza segno o se E1 ha un tipo con segno e un valore non negativo, il valore del risultato è la parte integrale del quoziente di E1/2^E2.Se E1 ha un tipo con segno e un valore negativo, il valore risultante è definito dall'implementazione.

Lo spostamento a destra per valori non negativi senza segno e con segno è piuttosto semplice;i bit vuoti sono riempiti con zeri. Per valori negativi con segno il risultato dello spostamento a destra è definito dall'implementazione. Detto questo, la maggior parte delle implementazioni come GCC e Visual C++ implementare lo spostamento a destra come spostamento aritmetico preservando il bit del segno.

Conclusione

A differenza di Java, che ha un operatore speciale >>> per uno spostamento logico diverso dal solito >> E <<, C e C++ hanno solo lo spostamento aritmetico con alcune aree lasciate indefinite e definite dall'implementazione.Il motivo per cui li considero aritmetici è dovuto alla formulazione standard dell'operazione matematicamente piuttosto che trattare l'operando spostato come un flusso di bit;questo è forse il motivo per cui lascia quelle aree non/implementate definite invece di definire semplicemente tutti i casi come cambiamenti logici.

In termini del tipo di spostamento che ottieni, la cosa importante è il tipo di valore che stai spostando.Una classica fonte di bug è quando si sposta un valore letterale, ad esempio, per mascherare i bit.Ad esempio, se volessi eliminare la parte più a sinistra di un intero senza segno, potresti provare questa maschera:

~0 >> 1

Sfortunatamente, questo ti metterà nei guai perché la maschera avrà tutti i suoi bit impostati perché il valore che viene spostato (~0) è firmato, quindi viene eseguito uno spostamento aritmetico.Invece, vorresti forzare un cambiamento logico dichiarando esplicitamente il valore come senza segno, cioèfacendo qualcosa del genere:

~0U >> 1;

Ecco le funzioni per garantire lo spostamento a destra logico e lo spostamento a destra aritmetico di un int in C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}

Quando lo fai - spostamento a sinistra di 1 si moltiplichi per 2 - shift destra per 1 dividi per 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)

Bene, ho guardato lo trovi su Wikipedia, e hanno questo da dire:

C, tuttavia, ha un solo operatore a turni destro, >>.Molti compilatori C scelgono quale cambio giusto eseguire in base al tipo di numero intero;I numeri interi firmati spesso vengono spostati usando lo spostamento aritmetico e i numeri interi non firmati vengono spostati usando lo spostamento logico.

Quindi sembra che dipenda dal tuo compilatore.Sempre in quell'articolo, nota che lo spostamento a sinistra è lo stesso per l'aritmetica e la logica.Consiglierei di fare un semplice test con alcuni numeri con segno e senza segno sul caso limite (ovviamente impostato con bit alti) e vedere quale è il risultato sul tuo compilatore.Consiglierei anche di evitare di dipendere dall'uno o dall'altro poiché sembra che C non abbia uno standard, almeno se è ragionevole e possibile evitare tale dipendenza.

Tasto maiuscolo di sinistra <<

Questo è in qualche modo semplice e ogni volta che usi l'operatore shift, è sempre un'operazione bit-wise, quindi non possiamo usarlo con un'operazione double e float.Ogni volta che lasciamo lo spostamento di uno zero, viene sempre aggiunto al bit meno significativo (LSB).

Ma nel turno giusto >> dobbiamo seguire una regola aggiuntiva e quella regola si chiama "copia del bit del segno".Il significato di "copia del bit del segno" è se il bit più significativo (MSB) viene impostato quindi, dopo uno spostamento a destra, nuovamente il MSB verrà impostato se è stato ripristinato, quindi verrà nuovamente ripristinato, significa che se il valore precedente era zero, dopo lo spostamento di nuovo, il bit è zero, se il bit precedente era uno, dopo lo spostamento è di nuovo uno.Questa regola non è applicabile per uno spostamento a sinistra.

L'esempio più importante sullo spostamento a destra se si sposta qualsiasi numero negativo sullo spostamento a destra, dopo alcuni spostamenti il valore raggiunge finalmente lo zero e successivamente se si sposta questo -1 un numero qualsiasi di volte il valore rimarrà lo stesso.Si prega di controllare.

gcc utilizzerà tipicamente gli spostamenti logici su variabili senza segno e per gli spostamenti a sinistra su variabili con segno.Lo spostamento aritmetico a destra è quello veramente importante perché segnerà l'estensione della variabile.

gcc lo utilizzerà quando applicabile, come probabilmente faranno altri compilatori.

Il GCC lo fa

for -ve -> Shift aritmetico
Per +ve -> Spostamento logico

Secondo molti C compilatori:

<< è uno spostamento a sinistra aritmetico o uno spostamento a sinistra bit a bit.
>> è uno spostamento a destra aritmetico o uno spostamento a destra bit per bit.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow