nicht angemeldet
Hallo,
Andere Variante:
Man subtrahiert einfach 1 von der Ausgangszahl und macht dann eine logische Und-Verknüpfung mit derselben. Wenn das Ergebnis 0 ist, ist die Ausgangszahl eine Zweierpotenz (leider incl. 2 hoch 0 = 1), sonst nicht.
Das ergibt sich unmittelbar aus der Tatsache, dass rechts des höchsten Bit nur noch Nullen stehen (bei Zweierpotenzen). Durch Subtraktion von 1 werden diese alle zu 1, während das vorher höchste Bit zu 0 wird, was durch die Und-Verknüpfung mit der Ausgangszahl zu insgesamt 0 führen muss.
Andererseits führt die Subtraktion von 1 nicht zu einer Änderung des höchsten Bit, wenn die Ausgangszahl keine Zweierpotenz ist, so dass die anschließende Und-Verknüfung auch nicht zu insgesamt 0 führen kann.
Die Vergleich lautet also:
(n-1)&n == 0
Er liefert true für Zweierpotenzen n > 1, sonst false.
Das scheint jetzt nun wirklich zu funktionieren. Habe es in vielen Varianten ausprobiert und es ergibt sich schon rein durch die Logik.
Gruß, Don P
Der Martin