Perché JDK usa lo spostamento invece di moltiplicare/dividere?

Question

Ho la seguente domanda:

Se viene chiesto se utilizzare uno spostamento rispetto a un moltiplicare o dividere, ad esempio la risposta sarebbe, lasciare ottimizzare la JVM.

Esempio qui: is-shifting-bits-faster-than-multiplying

Ora stavo guardando la fonte JDK, per esempio Priority Queue e il codice utilizza spostando solo sia per moltiplicazione e divisione (firmato e non firmato).

dando per scontato che il posto in SO è la risposta valida Mi chiedevo perché in JDK preferiscono farlo spostando?

E 'un po' sottili dettagli estranei a prestazioni? Sospetto che debba avere qualcosa a che fare con la moltiplicazione e la divisione di over/underflow ma non ne sono sicuro.

Qualcuno ha un'idea? I problemi di overflow sono gestiti meglio utilizzando lo spostamento? O è solo una questione di gusti?

Answer 1

penso lo fanno in questo esempio specifico per utilizzare il bit del segno. Java non ha tipi non firmati, quindi non è possibile emulare a >>> 1 con a /= 2 per i numeri che utilizzano il bit più significativo. Nota come il codice utilizza solo >>> durante l'esempio. Sono ragionevolmente certo che questo serva a sfruttare appieno l'intera gamma di bit.

Answer 2

È più una questione di gusti. Alcune persone sono così abituate alle operazioni binarie che sono più native per loro (personalmente uso anche questo codice che sto scrivendo per me stesso). Tuttavia dal punto di vista delle prestazioni i due si comportano allo stesso modo (l'ottimizzazione avviene in fase di compilazione, quindi l'uso dei turni migliorerà il tempo di compilazione, ma con una frazione minore e si può trascurare).

EDIT E come spesso accade c'è qualcosa di nuovo ho imparato da ogni risposta dò: considerare this. Dimostra perché la divisione per due non può sempre essere ottimizzata per il cambio. Quindi il mio commento sopra è quasi completamente sbagliato, a patto che java non ha tipi non firmati.

Answer 3

Alcuni validi motivi per preferire lo spostamento in Java:

• Se c'è una possibilità che si può essere in esecuzione in un ambiente non ottimizzato e non è possibile garantire che il compilatore JIT farà la ottimizzazione necessaria per te. Questo è probabilmente raro al giorno d'oggi, ma potrebbe ancora accadere in alcune circostanze.
• Se siete veramente facendo manipolazioni bit piuttosto che operazioni numeriche - è più evidente nel codice sorgente di utilizzare turni direttamente
• Se volete operazioni senza segno (ad esempio, si può facilmente fare turni non firmati, ma divisioni non firmate)

Answer 4

A parte lo spostamento più veloce della divisione sulla maggior parte dei sistemi. Il >>> esegue un'operazione non firmata, che divisione non ha. per esempio. se si desidera il punto centrale di due valori, è necessario utilizzare >>> per evitare un overflow. (Vedi Arrays.binaryCerca per codice simile)