Die folgende Funktion soll auswerten, ob eine Zahl ganzzahlige Potenz von 4 ist. Ich verstehe nicht ganz, wie es funktioniert?werte aus, ob eine Zahl eine ganzzahlige Potenz von 4 ist
bool fn(unsigned int x)
{
if (x == 0) return false;
if (x & (x - 1)) return false;
return x & 0x55555555;
}
Die erste Bedingung schließt 0 aus, was offensichtlich keine Potenz von 4 ist, aber die folgenden zwei Tests falsch bestehen würde. (EDIT:.. Nein, wäre es nicht, wie darauf hingewiesen Der erste Test ist redundant)
Die nächste ist ein netter Trick: Es gibt true zurück, wenn und nur wenn die Zahl eine Potenz von 2 ist. Eine Zweierpotenz ist dadurch gekennzeichnet, dass nur ein Bit gesetzt ist. Eine Zahl mit einem gesetzten Bit minus eins ergibt eine Zahl, bei der alle Bits vor diesem Bit gesetzt sind (d. H. 0x1000 minus Eins ist 0x0111). UND diese beiden Zahlen, und Sie erhalten 0. In jedem anderen Fall (d. H. Nicht Leistung von 2), wird es mindestens ein Bit, das sich überschneidet.
Deshalb an dieser Stelle wissen wir, es ist eine Potenz von 2
x & 0x55555555 kehrt nicht-Null (= true), wenn eine noch biß gesetzt (Bit 0, Bit 2, Bit 4, Bit 6, usw.). Das bedeutet, es ist eine Potenz von 4 (d. H. 2 passiert nicht, aber 4 Passes, 8 Passes, 16 Passes usw.).
Jede Leistung von 4 muß durch eine gerade Anzahl von Nullen (binäre Darstellung), gefolgt in der Form von 1: 100 ... 00:
100 = 4
10000 = 16
1000000 = 64
Der erste Test ("if") ist offensichtlich.
Wenn 1 aus einer Anzahl der Form Subtrahieren XY100 ... 00 Sie erhalten XY011 ... 11. Der zweite Test prüft also, ob es mehr als ein "1" -Bit in der Anzahl gibt (XY in diesem Beispiel).
Der letzte Test prüft, ob diese einzelne "1" an der richtigen Position ist, d. H. Bit # 2,4,6 usw. Wenn nicht, gibt die Maskierung (&) ein Ergebnis ungleich Null zurück.
x & (x - 1) entfernt das niedrigste 1 Bit von einer Zahl. – starblue