Ich verstehe, dass (2 * i == (i ^ (i - 1) + 1) in Java mich finden lässt, wenn eine Zahl eine Potenz von zwei ist. Aber kann jemand erklären, warum das funktioniert?
2 * i == (i ^ (i-1)) + 1
Grundsätzlich, wenn i eine Potenz von 2 ist, würde es ein einzelnes 1 in seinem Bitmuster haben. Wenn man davon 1 subtrahiert, werden alle unteren Bits dieses 1 Bits 1 , und dieses Zweierpotenz-Bit wird 0. Dann tust du XOR auf den Bits, was eine all 1 ergibt Bitmuster. Sie addieren 1 dazu, und Sie erhalten die nächste Macht von 2.
Merken Sie sich die XOR-Wahrheitstabelle:
%Vor%Beispiel:
Nehmen wir an, dass i 256 ist, was dieses Bitmuster ist.
Hier ist ein Beispiel, wenn Ihnen keine Stärke von 2 angezeigt wird
%Vor%Vereinfachte Version
Außerdem gibt es eine modifizierte Version dieser Überprüfung, um festzustellen, ob eine positive, vorzeichenlose Ganzzahl eine Potenz von 2 ist.
%Vor%Im Grunde gleiche Begründung
Wenn i eine Potenz von 2 ist, hat es ein einzelnes 1 -Bit in seiner Bitdarstellung. Wenn Sie 1 davon subtrahieren, wird das Bit 1 0 und alle unteren Bits werden 1 . Dann erzeugt AND ein all 0 -Bitmuster.
Das wichtige Bit ist das i ^ (i-1) (ich nehme an, das ist ein kleiner Tippfehler in der Frage). Angenommen, ich ist eine Potenz von 2. Dann ist ihre binäre Expansion eine 1 gefolgt von vielen Nullen. i-1 ist eine Zahl, bei der die führende 1 durch eine Null ersetzt wird und alle Nullen durch Einsen ersetzt werden. Das Ergebnis des XOR ist also eine Folge von Einsen, das ist die gleiche Anzahl von Bits wie ich.
Wenn andererseits i keine Potenz von 2 ist, werden durch das Subtrahieren von 1 nicht alle diese Bits umgedreht - der Xor identifiziert dann, welche Bits nicht von einer Stelle zur nächsten übertragen wurden, wenn Sie subtrahiert wurden 1. Es wird eine Null im Ergebnis des Xors geben. Wenn Sie also die 1 hinzufügen, wird sie nicht in die nächste Bitposition übertragen.