Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)?

[Der Martin]

Hallo Don,

Zweierpotenzen haben ja die Eigenschaft, in Binärdarstellung genau eine 1 aufzuweisen (das höchste Bit).

auf diesem Trip war ich auch schon; mir wollte nur auf die Schnelle noch kein Algorithmus einfallen, der genau das herausbekommt. Gut, wenn ich den Zahlenbereich kenne und weiß, dass die Zahl intern mit maximal k Bits dargestellt wird, kann ich k-mal hergehen und das LSB prüfen, dann die Zahl um ein Bit rechtsschieben und erneut prüfen. Wenn ich damit mehr als ein gesetztes Bit finde, ist es keine Zweierpotenz.

Es sei m die in PHP größtmögliche Zahl, die in Binärdarstellung nur Einsen aufweist, welche das auch immer sein mag ;-), also Binärzahl wie 11111111...

You are on the wooden way. ;-)

Dann liefert IMHO der Vergleich
~(n^m) == n
true, falls n eine Zweierpotenz ist, andernfalls false.

Nein, dieser Ausdruck liefert dann immer true. Denn die XOR-Verknüpfung mit dem vorzeichenlos größten darstellbaren Wert ist, banal ausgedrückt, eine bitweise Negation. Mit dem Operator ~ negierst du den Ausdruck ein zweites Mal und bekommst so wieder n heraus. qed.

So long,
 Martin