Giusto spostamento di bit che fornisce risultati errati, qualcuno può spiegare

Sto spostando a destra -109 per 5 bit, e mi aspetto -3, perché -109 = -1101101 (binario) spostamento a destra di 5 bit -1101101 >> 5 = -11 (binario) = -3

Ma, sto ottenendo -4 invece. Qualcuno potrebbe spiegare cosa c’è che non va?

Codice che ho usato:

int16_t a = -109; int16_t b = a >> 5; printf("%d %d\n", a,b); 

Ho usato GCC su linux e clang su osx, lo stesso risultato.

Il fatto è che non stai considerando la rappresentazione dei numeri negativi correttamente. Con lo spostamento verso destra, il tipo di spostamento (aritmetico o logico) dipende dal tipo di valore che viene spostato. Se lanci il tuo valore su un valore senza segno, potresti ottenere ciò che ti aspetti:

 int16_t b = ((unsigned int)a) >> 5; 

Stai utilizzando -109 (16 bit) nell’esempio. 109 in bit è:

 00000000 01101101 

Se prendi il complemento 109 2 ottieni:

 11111111 10010011 

Quindi, hai ragione spostando per 5 il numero 11111111 10010011 :

 __int16_t a = -109; __int16_t b = a >> 5; // arithmetic shifting __int16_t c = ((__uint16_t)a) >> 5; // logical shifting printf("%d %d %d\n", a,b,c); 

Produrrà:

 -109 -4 2044 

Il risultato del giusto spostamento di un valore negativo è il comportamento definito dall’implementazione, dalla bozza standard C99 sezione 6.5.7 Operatori di cambio 6.5.7 paragrafo 5 che dice ( enfatizza il mio futuro ):

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

Se guardiamo i documenti di comportamento definiti gcc di gcc C nella sezione Interi , dice:

I risultati di alcune operazioni bit a bit sugli interi con segno (C90 6.3, C99 e C11 6.5).

Gli operatori bit a bit agiscono sulla rappresentazione del valore includendo sia il segno che i bit di valore, in cui il bit del segno viene considerato immediatamente al di sopra del bit del valore più alto. Firmato ‘>>’ agisce su numeri negativi per estensione del segno.

Questo è abbastanza chiaro cosa sta succedendo, quando si rappresentano gli interi firmati, gli interi negativi hanno una proprietà che è, l’estensione del segno e il bit più significativo a sinistra è il bit del segno.

Quindi, 1000 … 0000 (32 bit) è il numero negativo più grande che puoi rappresentare, con 32 bit.

Per questo, quando si ha un numero negativo e si passa a destra, accade una cosa chiamata estensione del segno, il che significa che il bit più significativo a sinistra viene esteso, in termini semplici significa che, per un numero come -109 questo è ciò che accade :

Prima di cambiare hai (16 bit):

1111 1111 1001 0011

Quindi sposta a destra 5 bit (dopo che i pipe sono i bit scartati):

1XXX X111 1111 1100 | 1 0011

Le X sono i nuovi spazi che appaiono nella rappresentazione del bit intero, che a causa dell’estensione del segno, sono pieni di 1, che ti danno:

1111 1111 1111 1100 | 1 0011

Quindi spostando: -109 >> 5, ottieni -4 (1111 …. 1100) e non -3.

Conferma dei risultati con il complemento 1:

+3 = 0 … 0000 0011

-3 = ~ (0 … 0000 0011) + 1 = 1 … 1111 1100 + 1 = 1 … 1111 1101

+4 = 0 … 0000 0100

-4 = ~ (0 … 0000 0100) + 1 = 1 … 1111 1011 + 1 = 1 … 1111 1100

Nota: Ricorda che il complemento 1 è proprio come il complemento a 2 con la differenza che devi prima negare i bit del numero positivo e solo poi sumre +1.

La risposta di Pablo è sostanzialmente corretta, ma ci sono due piccoli bit (nessun gioco di parole!) Che può aiutarti a vedere cosa sta succedendo.

C (come praticamente ogni altro linguaggio) usa il cosiddetto complemento a due, che è semplicemente un modo diverso di rappresentare numeri negativi (è usato per evitare i problemi che si presentano con altri modi di gestire numeri negativi in ​​binario con un numero fisso di cifre ). C’è un processo di conversione per trasformare un numero positivo in complemento a due (che sembra proprio come qualsiasi altro numero in binario – eccetto che il bit più lontano più a sinistra deve essere 0 in un numero positivo, è fondamentalmente il segnaposto del segno) è ragionevolmente semplice computazionalmente:

Prendi il tuo numero

00000000 01101101 (Ha 0s che lo riempie a sinistra perché è di 16 bit. Se fosse lungo, sarebbe riempito con più zeri, ecc.)

Capovolgi i bit

11111111 10010010

Aggiungi uno.

11111111 10010011.

Questo è il numero di complementi a due che Pablo si riferiva a. È come C detiene -109, bit a bit.

Quando lo spostate logicamente a destra di cinque bit, sembrerebbe che venga visualizzato

00000111 11111100.

Questo numero non è assolutamente -4. (Non ha un 1 nel primo bit, quindi non è negativo, ed è troppo grande per essere 4 di magnitudine.) Perché C ti dà 4 negativo allora?

La ragione è fondamentalmente che l’implementazione ISO per C non specifica come un determinato compilatore debba trattare il bit shifting in numeri negativi. GCC fa ciò che si chiama estensione del segno: l’idea è di basare fondamentalmente i bit di sinistra con 1 s (se il numero iniziale era negativo prima dello spostamento) o 0 (se il numero iniziale era positivo prima dello spostamento).

Quindi, invece dei 5 zeri che si sono verificati nel turno di bit precedente, ottieni invece:

11111111 11111100. Quel numero è in effetti negativo 4! (Che è quello che ricevevi costantemente come risultato.)

Per vedere che questo è in effetti -4, puoi semplicemente riconvertirlo in un numero positivo usando di nuovo il metodo del complemento a due:

00000000 00000011 (bit capovolti) 00000000 00000100 (aggiungere uno).

Sono quattro, quindi il tuo numero originale (11111111 11111100) era -4.