Spiegazione della media sicurezza di due numeri

Question

Ogni volta che ho bisogno di una media di due numeri per un algoritmo come la ricerca binaria, ho sempre fare qualcosa di simile:

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).

Answer 1

Consideriamo quindi i byte anziché gli interi. L'unica differenza è che un byte è un numero intero a 8 bit, mentre un int ha 32 bit. In Java, entrambi sono sempre firmati, il che significa che il bit iniziale indica se sono positivi (0) o negativi (1).

byte low = Byte.valueOf("01111111", 2); // The maximum byte value 
byte high = low; // This copies low. 

byte sum = low + high; // The bit representation of this is 11111110, which, having a 
         // leading 1, is negative. Consider this the worst case 
         // overflow, since low and high can't be any larger. 

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow. 

Per ints, è la stessa cosa. Fondamentalmente il succo di tutto ciò è che l'utilizzo di un bithift non firmato su interi con segno consente di sfruttare il bit iniziale per gestire i valori più elevati possibili di basso e alto.

Answer 2

Non è possibile utilizzare un int unsigned in Java. In caso di overflow, vengono considerati i 32 bit bassi e i bit di ordine alto vengono scartati. Lo spostamento a destra senza segno ti aiuterà a trattare l'int come unsigned int. Tuttavia, in C++ non avrai l'overflow.

Answer 3

La versione C++ non risolve il problema di overflow. Risolve solo il problema di dividere con successo per 2 usando shift invece di /, un'ottimizzazione che il tuo compilatore dovrebbe essere in grado di fare da sola se si trattasse di un miglioramento delle prestazioni.

D'altro canto, l'overflow può non essere un problema reale, se i tipi interi sono sufficientemente grandi da contenere un intervallo ragionevole di indici.

Answer 4

siete al sicuro da integer overflow utilizzando il modo in cui lei ha detto che già utilizzate, che è:

int mid = low + ((high - low)/2); 

Let si compilatore farlo proprio lavoro per ottimizzare questo se è necessario.

Answer 5

La versione C++ ha un trucco nascosto: low e high sono int s ma non sono mai negativi. Quando li trasmetti a unsigned int, il tuo bit di segno diventa un bit di precisione extra, che una singola aggiunta non può eccedere.

Non è un trucco molto buono perché gli indici di array dovrebbero essere unsigned in ogni caso.

Come è stato detto altrove, i >> 1 significa /2 per gli interi senza segno.

Answer 6

Il codice che hai visto è rotto: non calcola correttamente la media dei numeri negativi. Se stai operando solo su valori non negativi, come gli indici, va bene, ma non è una sostituzione generale. Il codice si ha in origine,

int mid = low + ((high - low)/2); 

non è al sicuro da troppo pieno o perché la differenza high - low potrebbe traboccare il campo per gli interi con segno. Di nuovo, se lavori solo con numeri interi non negativi, va bene.

sfruttando il fatto che A+B = 2*(A&B) + A^B possiamo calcolare la media di due numeri interi senza troppo pieno in questo modo:

int mid = (high&low) + (high^low)/2; 

È possibile calcolare la divisione per 2 utilizzando un cambiamento po ', ma tenere a mente i due non la sono lo stesso: la divisione arrotonda verso 0 mentre il bit shift si arrotonda sempre verso il basso.

int mid = (high&low) + ((high^low)>>1);