Qual è la differenza tra lo spostamento del bit e le operazioni aritmetiche?

Question

int aNumber; 

aNumber = aValue/2; 
aNumber = aValue >> 1; 

aNumber = aValue * 2; 
aNumber = aValue << 1; 

aNumber = aValue/4; 
aNumber = aValue >> 2; 

aNumber = aValue * 8; 
aNumber = aValue << 3; 

// etc. 

Qual è il modo "migliore" per eseguire le operazioni? Quando è meglio usare il cambio di bit?

Answer 1

I due sono funzionalmente equivalenti negli esempi forniti (ad eccezione di quello finale, che deve essere letto aValue * 8 == aValue << 3), se si utilizzano gli interi positivi . Questo è solo in caso moltiplicando o dividendo per poteri di 2.

Lo spostamento di bit non è mai più lento dell'aritmetica. A seconda del compilatore, la versione aritmetica può essere compilata nella versione bit-shifting, nel qual caso entrambi sono altrettanto efficienti. In caso contrario, lo spostamento di bit dovrebbe essere significativamente più veloce dell'aritmetica.

La versione aritmetica è spesso più leggibile, tuttavia. Di conseguenza, io uso la versione aritmetica in quasi tutti i casi, e utilizzare solo po 'spostando se profiling rivela che la dichiarazione è in un collo di bottiglia:

programmi dovrebbe essere scritto per le persone a leggere, e solo incidentalmente per le macchine da eseguire .

Answer 2

Se si dispone di grandi calcoli in un tipo di ambiente a ciclo chiuso in cui la velocità di calcolo ha un impatto --- utilizzare le operazioni di bit. (considerato più veloce delle operazioni aritmetiche)

Answer 3

Quando è circa 2 numeri di potenza (2^x), è meglio utilizzare i turni - è solo per "spingere" i bit. (1 operazione di assemblaggio invece di 2 in divisione).

C'è qualche linguaggio che il suo compilatore fa questa ottimizzazione?

Answer 4

Lo spostamento dei bit è un'operazione "vicina al metallo" che la maggior parte delle volte non contiene alcuna informazione su ciò che si vuole veramente ottenere.

Se si desidera dividere un numero per due, con qualsiasi mezzo, scrivere x/2. Capita di essere raggiunto da x >> 1, ma quest'ultimo nasconde l'intento.

Quando risulta essere un collo di bottiglia, rivedere il codice.

Answer 5

La differenza è che le operazioni aritmetiche hanno risultati chiaramente definiti (a meno che non si eseguano in overflow con segno). Le operazioni Shift non hanno risultati definiti in molti casi. Sono chiaramente definiti per i tipi non firmati sia in C che in C++, ma con tipi firmati le cose si complicano rapidamente.

In linguaggio C++ il significato aritmetico di spostamento a sinistra << per i tipi firmati non è definito. Cambia solo bit, riempiendo di zeri a destra. Ciò che significa in senso aritmetico dipende dalla rappresentazione firmata utilizzata dalla piattaforma. Virtualmente lo stesso vale per l'operatore >> a destra. Spostando i valori negativi verso destra si ottengono risultati definiti dall'implementazione.

In linguaggio C le cose sono definite in modo leggermente diverso. I valori negativi a spostamento di sinistra sono impossibili: conducono a comportamenti non definiti. Spostando i valori negativi verso destra si ottengono risultati definiti dall'implementazione.

Sulla maggior parte delle implementazioni pratiche ogni singolo spostamento di destra esegue la divisione per 2 con arrotondamento verso l'infinito negativo.Questo, BTW, è notevolmente diverso dalla divisione aritmetica / da 2, poiché tipicamente (e sempre in C99) del tempo tondo verso 0.

Per quanto riguarda quando si deve usare il bit shifting ... Bit- lo spostamento è per operazioni che funzionano a bit. Gli operatori di spostamento di bit sono usati molto raramente come sostituto degli operatori aritmetici (ad esempio, non si dovrebbero mai usare turni per eseguire la moltiplicazione/divisione per costante).

Answer 6

Finché si sta moltiplicando o dividendo entro i poteri 2er è più veloce operare con uno spostamento perché è una singola operazione (richiede solo un ciclo di processo).
Uno si abitua a leggere < < 1 come * 2 e >> 2 as/4 abbastanza rapidamente, quindi non sono d'accordo con la leggibilità che va via quando si usa lo spostamento, ma questo dipende da ogni persona.

Se volete conoscere maggiori dettagli su come e perché, forse wikipedia può aiutare o se si vuole passare attraverso il dolore imparare assemblaggio ;-)

Answer 7

Che cosa è il modo "migliore" per fare operazioni?

Utilizzare le operazioni aritmetiche quando si tratta di numeri. Usa le operazioni di bit quando si ha a che fare con i bit. Periodo. Questo è buon senso. Dubito che qualcuno potrebbe mai pensare di usare operazioni di shift in bit per intere o doppie come una normale cosa di tutti i giorni è una buona idea.

Quando è preferibile utilizzare lo spostamento di bit?

Quando si tratta di bit?

Domanda aggiuntiva: si comportano allo stesso modo in caso di overflow aritmetico?

Sì. Le operazioni aritmetiche appropriate sono (spesso, ma non sempre) semplificate per le loro controparti bit shift dalla maggior parte dei compilatori moderni.

Modifica: La risposta è stata accettata, ma voglio solo aggiungere che c'è un sacco di consigli sbagliati in questa domanda. Non dovresti mai (leggi: quasi mai) usare operazioni di shift di bit quando si ha a che fare con gli inte. È una pratica orribile.

Answer 8

Quando il tuo obiettivo è moltiplicare alcuni numeri, usare gli operatori aritmetici ha senso.

Quando i tuoi obiettivi sono effettivamente spostare i bit logicamente, quindi utilizzare gli operatori di spostamento.

Per esempio, diciamo che si stanno dividendo le componenti RGB da una parola RGB, questo codice ha un senso:

int r,g,b; 
short rgb = 0x74f5; 
b = rgb & 0x001f; 
g = (rgb & 0x07e0) >> 5; 
r = (rgb & 0xf800) >> 11; 

d'altra parte quando si vuole moltiplicare certo valore con 4 si dovrebbe davvero codificare il vostro intento e non fare turni.

Answer 9

Come esempio delle differenze, questo è assembly x86 creata usando gcc 4.4 con -O3

int arithmetic0 (int aValue) 
{ 
    return aValue/2; 
} 

00000000 <arithmetic0>: 
    0: 55      push %ebp 
    1: 89 e5     mov %esp,%ebp 
    3: 8b 45 08    mov 0x8(%ebp),%eax 
    6: 5d      pop %ebp 
    7: 89 c2     mov %eax,%edx 
    9: c1 ea 1f    shr $0x1f,%edx 
    c: 8d 04 02    lea (%edx,%eax,1),%eax 
    f: d1 f8     sar %eax 
    11: c3      ret  

int arithmetic1 (int aValue) 
{ 
    return aValue >> 1; 
} 

00000020 <arithmetic1>: 
    20: 55      push %ebp 
    21: 89 e5     mov %esp,%ebp 
    23: 8b 45 08    mov 0x8(%ebp),%eax 
    26: 5d      pop %ebp 
    27: d1 f8     sar %eax 
    29: c3      ret  

int arithmetic2 (int aValue) 
{ 
    return aValue * 2; 
} 

00000030 <arithmetic2>: 
    30: 55      push %ebp 
    31: 89 e5     mov %esp,%ebp 
    33: 8b 45 08    mov 0x8(%ebp),%eax 
    36: 5d      pop %ebp 
    37: 01 c0     add %eax,%eax 
    39: c3      ret  

int arithmetic3 (int aValue) 
{ 
    return aValue << 1; 
} 

00000040 <arithmetic3>: 
    40: 55      push %ebp 
    41: 89 e5     mov %esp,%ebp 
    43: 8b 45 08    mov 0x8(%ebp),%eax 
    46: 5d      pop %ebp 
    47: 01 c0     add %eax,%eax 
    49: c3      ret  

int arithmetic4 (int aValue) 
{ 
    return aValue/4; 
} 

00000050 <arithmetic4>: 
    50: 55      push %ebp 
    51: 89 e5     mov %esp,%ebp 
    53: 8b 55 08    mov 0x8(%ebp),%edx 
    56: 5d      pop %ebp 
    57: 89 d0     mov %edx,%eax 
    59: c1 f8 1f    sar $0x1f,%eax 
    5c: c1 e8 1e    shr $0x1e,%eax 
    5f: 01 d0     add %edx,%eax 
    61: c1 f8 02    sar $0x2,%eax 
    64: c3      ret  

int arithmetic5 (int aValue) 
{ 
    return aValue >> 2; 
} 

00000070 <arithmetic5>: 
    70: 55      push %ebp 
    71: 89 e5     mov %esp,%ebp 
    73: 8b 45 08    mov 0x8(%ebp),%eax 
    76: 5d      pop %ebp 
    77: c1 f8 02    sar $0x2,%eax 
    7a: c3      ret  

int arithmetic6 (int aValue) 
{ 
    return aValue * 8; 
} 

00000080 <arithmetic6>: 
    80: 55      push %ebp 
    81: 89 e5     mov %esp,%ebp 
    83: 8b 45 08    mov 0x8(%ebp),%eax 
    86: 5d      pop %ebp 
    87: c1 e0 03    shl $0x3,%eax 
    8a: c3      ret  

int arithmetic7 (int aValue) 
{ 
    return aValue << 4; 
} 

00000090 <arithmetic7>: 
    90: 55      push %ebp 
    91: 89 e5     mov %esp,%ebp 
    93: 8b 45 08    mov 0x8(%ebp),%eax 
    96: 5d      pop %ebp 
    97: c1 e0 04    shl $0x4,%eax 
    9a: c3      ret  

Le divisioni sono diversi - con la rappresentazione di un complemento a due, spostando un numero dispari negativo giusto si traduce in una valore diverso per dividerlo per due. Ma il compilatore ottimizza ancora la divisione in una sequenza di turni e aggiunte.

La differenza più ovvia è che questa coppia non fa la stessa cosa: cambiare per quattro equivale a moltiplicare per sedici, non otto! Probabilmente non otterresti un bug da questo se lascia che il compilatore sudizzi le piccole ottimizzazioni per te.

aNumber = aValue * 8; 
aNumber = aValue << 4; 

Answer 10

int i = -11; 
std::cout << (i/2) << '\n'; // prints -5 (well defined by the standard) 
std::cout << (i >> 1) << '\n'; // prints -6 (may differ on other platform) 

A seconda del comportamento di arrotondamento desiderato, si può preferire uno sopra l'altro.