Ja, (low + high) >> 1 ausfließen kann, wenn die Summe hoch genug ist. Wie Sie wissen, ist >>> für unsigned, so dass es immer in 0 auf der wichtigsten Seite verschiebt. Dies erweist sich als sehr wichtig, falls es überläuft.
Der Trick, (low + high) sogar mit Überlauf zu verwenden, ist, dass Informationen noch behalten werden. Wenn es überläuft, ist die maximal mögliche mathematische Summe immer noch Integer.MAX_VALUE * 2, die immer noch als unsigned int dargestellt werden könnte, wenn Java eins hätte. Aber wir können behandeln die Summe als unsigned int beim Dividieren von 2 mit dem unsigned rechten Shift-Operator, >>>. Wenn Bit-Verschiebung nach rechts durch 1 erfolgt, können wir die Summe als unsigned behandeln int, "un-überläuft" die int.
Mit >> hier wird nicht funktionieren, wenn die Summe überläuft, weil sie in eine negative Zahl überläuft und >> wird in einem 1 verschieben, halten Sie den Wert negativ. Dies führt zu einer falschen Durchschnittsberechnung (2 positive Zahlen, deren Summenüberläufe zu einem negativen Durchschnitt führen).
Ob Sie >>> oder >> verwenden, Überlauf ist eine Möglichkeit. So können beide überlaufen. Aber nur >>> wird den Fall gut behandeln, die Summe "nicht überlaufen".
Der Trick
avg = (low & high) + ((low^high) >> 1);
ist eine andere Art und Weise der Berechnung des Durchschnitts, wenn die Summe überlaufen kann. Dies vermeidet den Überlauf vollständig. Dies zerlegt die Summe in 2 Teile - die "Übertrag" -Bits und die "Nicht-Übertrag" -Bits.
Bei der Addition werden die Bits zum nächsten höherwertigen Bit übertragen, wenn beide Bits gesetzt sind - low & high. Normalerweise müssen diese Bits auch nach links verschoben werden, aber wir berechnen den Durchschnitt von 2 Zahlen, also würden wir am Ende auch richtig verschieben. Das Nettoergebnis: keine Verschiebung hier.
die Bits, die nicht ausgeführt werden, sind entweder ein 1 wenn die Bits verschieden oder ein 0 sind, wenn die Bits gleich sind - das ist, wo (low^high) aus (XOR) kommt. Normalerweise werden diese Bits nicht verschoben, aber wir berechnen den Durchschnitt von 2 Zahlen, also würden wir am Ende auch richtig verschieben. Diese Verschiebung erscheint als >> 1.Die & und ^ Operatoren überlaufen nicht, so >> wird hier gut funktionieren.
Beispiel: Durchschnitt von 1100 (12) und 1010 (10)
1100 & 1010 = 1000
1100^1010 = 0110, 0110 >> 1 = 0011
1000 + 0011 = 1011 (11)