Logische Verschiebung nach rechts in binärer Such

Question

In einer binären Such Durchführung arithmetischer Überlauf zu verhindern, offensichtlich:

mid = (low + high)/2 

Überlauf führen kann. Ich habe eine Menge von Dokumentation (wie this) gelesen, dass das folgende Problem verhindert:

mid = (low + high) >>> 1 

Allerdings habe ich keinen Grund, warum das funktionieren würde. Kann jemand Licht darauf werfen?

Answer 1

Es gibt keine "logische Rechtsverschiebung" in C (es gibt keinen Operator >>>), also sprechen Sie wahrscheinlich über Java.

Dies funktioniert, weil low und high im Bereich von 0 bis 2^31-1 angenommen werden (vorausgesetzt, wir sprechen hier über int). Der maximal mögliche Wert von low+high ist nicht größer als 2^32-2 und ist somit durch einen unsigned int darstellbar (wenn so etwas in Java existierte). So etwas gibt es in Java nicht, also sind wir jetzt übergelaufen. Der logische Verschiebungsoperator >>> behandelt seinen Operanden jedoch so, als ob er vorzeichenlos wäre, so dass dies das erwartete Ergebnis ergibt.

Answer 2

>>> ist der vorzeichenlose Rechtsverschiebung-Operator in Java (ref). Da mid, low und high vorzeichenbehaftete Ganzzahlen sind, kann die Addition von low und high zu einem negativen Wert überlaufen. >>> ignoriert die mögliche negative Auswirkung dieses Ergebnisses und verschiebt es nach rechts, als ob es eine vorzeichenlose Zahl wäre (und in Java gibt es keine vorzeichenlosen Zahlen).

In C und C++, dann ist dies das Äquivalent von

mid = ((unsigned int)low + (unsigned int)high)) >> 1; 

(die explizit in dem Artikel erwähnt wird Ihnen verlinken auf).

Dieser endet als die gleiche wie

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

Beachten Sie, dass Sie wahrscheinlich nicht wollen, es so zu tun. Wenn Sie vorzeichenlose Werte verwenden, sollten Sie bei unsignierten Werten bleiben und vermeiden, zwischen signierten und unsignierten Daten hin- und herzuspringen.

Answer 3

die gleichen Link Staaten der Grund für Java verwenden >>> und Grund (niedrig + hoch) halten kann den Maximalwert ‚Mitte‘ nicht überschreiten:

In Programmierung Pearls Bentley sagt, dass die analoge Leitung "setzt m auf den Durchschnitt von l und u, gekürzt auf die nächste ganze Zahl." Auf der Seite Gesicht, könnte diese Behauptung korrekt erscheinen, aber es schlägt für große Werte der int-Variablen niedrig und hoch. Insbesondere schlägt es fehl, wenn die Summe von niedrig und hoch größer ist als der maximale positive int Wert (231 - 1). Die Summe fließt zu einem negativen Wert über, und der Wert bleibt negativ, wenn er durch zwei geteilt wird. In C verursacht dies einen Array-Index außerhalb der Grenzen mit unvorhersehbaren Ergebnissen.

Weiter heißt es, das Äquivalent operaiton in C:

......

In C und C++ (wo Sie den >>> Betreiber nicht haben), können Sie kann dies tun:

6: mid = ((unsigned int) tief + (unsigned int) hoch)) >> 1;

Also die Lösung ist es, diesen Artikel vollständig zu lesen und zu verstehen.

Answer 4

Wie in anderen Antworten erwähnt, ist >>> kein C Operator.

Wenn Sie jedoch in C Überlauf vermeiden möchten, können Sie dies versuchen:

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