Ogni volta che ho bisogno di una media di due numeri per un algoritmo come la ricerca binaria, ho sempre fare qualcosa di simile:Spiegazione della media sicurezza di due numeri
int mid = low + ((high - low)/2);
Recentemente ho visto un altro modo per farlo in this post, ma non lo capisco Si dice che si può fare questo in Java:
int mid = (low + high) >>> 1;
o questo in C++:
int mid = ((unsigned int)low + (unsigned int)high)) >> 1;
La versione C++ rende essenzialmente entrambi gli operandi non firmato, così facendo un risultato spostamento in uno spostamento aritmetico, invece di una firma cambio. Capisco cosa stanno facendo entrambi questi pezzi di codice, ma come risolve il problema dell'overflow? Ho pensato che l'intero problema era che il valore intermedio high + low
potrebbe traboccare?
Edit:
Oh, duh. Tutte le risposte non rispondevano esattamente alla mia domanda, ma è stata la risposta di @John Zeringue a farla scattare. Proverò a spiegare qui.
Il problema con (high + low)/2
in Java non è esattamente quello overflow di high + low
(è overflow poiché gli interi sono entrambi firmati, ma tutti i bit sono ancora lì e nessuna informazione è persa). Il problema con l'assunzione della media come questa è la divisione. La divisione opera su un valore con segno, quindi il risultato sarà negativo. L'uso dello spostamento invece dividerà per due ma considererà i bit al posto del segno (trattandolo in modo efficace come non firmato).
Java non ha numeri interi senza segno. Considera cosa succederebbe se il tuo 'int' tracimasse? Considera anche cosa fa ">>>". –
Ti suggerisco di provarlo e vedere che differenza fa. Questo è stato un problema noto per decenni, quindi potresti cercarlo ma imparerai di più capendolo da solo. –