Spostamento a destra per eseguire Divide per 2 On -1

Question

So che è possibile eseguire la divisione per 2 utilizzando il passaggio a destra.

Per semplicità, prendere un sistema numerico a 4 bit

-1 - 1111 
-2 - 1110 
-3 - 1101 
-4 - 1100 
-5 - 1011 
-6 - 1010 
-7 - 1001 
-8 - 1000 
7 - 0111 
6 - 0110 
5 - 0101 
4 - 0100 
3 - 0011 
2 - 0010 
1 - 0001 
0 - 0000 

Se provo a eseguire

6/2 = 0110 >> 1 = 0011 = 3 
-6/ 2 = 1010 >> 1 = 1101 = -3 

è valido per entrambi + ve -ve e il numero

Tuttavia, quando vengono a 1

1/2 = 0001 >> 1 = 0000 = 0 
-1/ 2 = 1111 >> 1 = 1111 = -1 

Sembra che ci sia un caso speciale in -1, come spostamento verso destra quindi per spostarlo all'infinito negativo.

Attualmente, ho bisogno di mettere uno speciale assegno, se per questo, come mi aspetto -1/2 = 0.

mi chiedevo come si fa a gestire questa eccezione ragazzo nel codice? Hai messo un check?

Answer 1

Qualsiasi numero dispari negativo non funzionerà. Comunque per rispondere alla tua domanda, se sai che puoi avere numeri negativi, basta dividere per 2. Questo è trasformato in uno spostamento con una correzione da parte del jit/compilatore.

Answer 2

Nel caso strano, entrambe le operazioni provocano un'operazione a pavimento nel risultato.

• 3/2 -> piano (1.5) => 1
• -3/2 -> piano (-1.5) => -2

Si potrebbe mettere un assegno, qualcosa di simile \

if (isOdd(number) && isNegative(number)) 
    result++; 

Answer 3

Se si fa spostamento di dividere per due, si finisce sempre "arrotondamento" verso il basso - verso lo zero se positivo, lontano da esso se negativo.

Se questo non è quello che si vuole è, è possibile correggere per esso:

if (n & 1 > 0 && n < 0) 
    result += 1; 

Answer 4

Odio dirlo, ma non lo gestisco nel mio codice, poiché non uso il bit shifting per la moltiplicazione o la divisione. Questo mi odora di un premature optimisation.

Perché pensi che sia necessario eseguire la divisione con lo spostamento dei bit anziché il più leggibile x/2?

Answer 5

@Anon è tecnicamente corretto.

Tuttavia, è best practice utilizzare l'operatore / per la divisione e lasciare la micro-ottimizzazione al compilatore JIT. Il compilatore JIT è in grado di ottimizzare le divisioni per costanti come shift/add sequenze ... quando questa è una cosa ottimale da fare per la piattaforma di esecuzione.

Fare questo tipo di cose è (probabilmente) un'ottimizzazione prematura, e potrebbe essere un anti-ottimizzazione se il tuo codice ha bisogno di essere eseguito velocemente su più piattaforme Java.

Answer 6

Mi sono annoiato un giorno e ho profilato divisioni contro turni per il potere di 2 cose; pensavo di pubblicarlo qui per chiunque fosse interessato.

Su HotSpot VM 1.6 su Windows, l'utilizzo di j /= 4 da -100000000 a 100000000 ha funzionato in circa 12 secondi mentre si utilizzava j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; in soli 2,5 secondi.

OpenJDK VM 1.6 su Linux ha ottenuto 5,5 s per le divisioni e 1,5 s per i turni.

Questo suggerirebbe che il compilatore JIT in realtà non fa nulla di eccezionale per la potenza di 2 divisione.

GCC è riuscito a ottimizzare la divisione in modo che fosse più veloce dei salti mortali e dei turni.

~(~j+1 >> 2) + 1 utilizza due complementi per capovolgere il numero, spostarlo e invertirlo.

long j = 0; 
for (long i = -100000000; i < 100000000; i++) { 
    j = i; 
    j /= 4; 
} 
System.out.println(j);` 

vs

long j = 0; 
for (long i = -100000000; i < 100000000; i++) { 
    j = i; 
    j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; 
} 
System.out.println(j);`