Manchmal tauchen in Foren richtig nette Sachen, die einen in Erstaunen setzen, wie schnell und einfach manches zu lösen ist. (siehe Thread)
Zwei interessante Fragen, die mich auch schon öfter beschäftigt haben sind hier mal erwähnt und als C++ Code wiedergegeben. Bisher habe ich diese immer mit einer entsprechenden Schleife und Shift-Operatoren gelöst.
1. Wie kann man schnell prüfen ob ein Integer eine 2er Potenz ist?
Der Algorithmus ist so verblüffend einfach, dass man sich fragen muss, warum man noch nicht von selbst drauf gekommen ist:
bool IsPowerOf2(int n)
{
return (n & (n - 1))==0;
}
Tricky: Wenn mehr als zwei Bits gesetzt sind, bleibt bei der gegebenen Arithmetik mindestens das höchste Bit stehen.
❗ Nach diesem Algorithmus ist 0 übrigens auch eine Power of 2!
2. Wie findet man die nächste 2er Potenz einer gegebenen Zahl?
Diese Frage stellt sich für mich immer wieder, wenn ich binäre Suchen durchführe.
Auch hier gibt es eine statische Lösung, die ich hier mal wiedergebe und die sowohl für 32bit als auch für 64bit funktioniert und direkt in entsprechende Assembler Befehle umgesetzt wird.
Der Code vermeidet einen 32bit shift, da das Ergebnis in einem 32bit C++ Compiler undefiniert ist (Warning C4293).
int GetNextPowerOf2(int n)
{
// Code works for 32bit and 64bit
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16; // Sufficient for 32bit
n |= n >> 16; // for a 64bit System we need a new 32bit shift (n>>32)
n |= n >> 16; // but this operation is undefined on a 32bit system
// so we use 2 16bit shifts. (C4293)
return n+1;
}
Oft genug wird das höchste gesetzte Bit gesucht. In diesem Fall einfach den Startwert oder das Ergebnis um eine Bitposition shiften.
Tricky: Das höchste Bit wird nach der Subtraktion einfach auf alle niederen Bits übertragen.
❗ Auch hier ist das Verhalten bei 0 eigentümlich. Die nächste 2er Potenz auf 0 ist mit diesem Algorithmus 0!
Die entsprechenden Algorithmen sind hier auf dieser Seite beschrieben:
http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_number_is_a_power_of_two
Zur Erkennung einer 2er-Potenz mein Vorschlag:
bool IsPow2(int n)
{ return !(n--&n); }
Wenn schon, denn schon. Dürfte etwas schneller als IsPowerOf2() sein, weil
1. Dekrement(--) mit Befehl DEC und nicht mit SUB umgesetzt wird und
2. Gleichheit(==) wird subtraktiv erkannt, das logische NOT(!) ist fixer!
Den Blogger finde ich gut, weiter so!
Thomas C. aus M. an der E.
Das kann nicht gehen.
!(n--&n)
liefert immer 0! Wenn Du es so lösen wolltest.
Über solche Details muss man sich keine Gedanken machen. Der Optimizer macht das hier schon richtig.