Prüfen, ob eine Zahl n eine 2er-Potenz ist.

Question

Hallo an alle!

Ich muss in einem Programm sehr schnell prüfen, ob eine ganze Zahl n eine 2er-Potenz ist. Natürlich könnte ich alle 2er-Potenzen abfragen, also

if (n==1 || n==2 | n==4 | ...) then ...

Aber das kann bei einer 64-Bit-Zahl schon sehr lange dauern.

Daher stelle ich die Frage im Matheboard in der Hoffnung, es gibt eine Formel für eine schnellere Prüfung.

;)

Answer 1

Aloha :)

Mit \(n=n \text{ and } (n-1)\) wird das niederwertigste 1-Bit einer Binärzahl auf 0 gesetzt und alle anderen Bits bleiben ungeändert. Mit "and" ist die binäre Und-Verknüpfung gemeint.

Wenn n eine 2er-Potenz ist, ist nur ein einziges Bit gesetzt. Wenn dieses gelöscht wird, ist der Wert 0. Daher kannst du in C schreiben:

if (0==n&n-1) //wahr, wenn n 2er-Potenz ist.

Comments

Achtung: EmNero hat eine Klitzekleinigkeit besser gemacht:

if (n == 0) return false;

Der Fragesteller sollte sich überlegen warum das notwendig ist, wenn man möchte das der Code für alle natürlichen Zahlen inkl. der Null gilt.

Answer 2

bool isPowerOfTwo(unsigned int n)
{
if (n == 0) return false;
if ((n & (n-1)) == 0) return true;
return false;
}

 So könnte die Funktion näherungsweise in C++ aussehen

Comments

Warum hast du nicht einfach

bool isPowerOfTwo(unsigned int n) {
   return ((n != 0) && ((n & (n-1)) == 0));
};

geschrieben. Oder hat das Nachteile im Laufzeitverhalten?

---

Deine Version würde ich in eigenem Code implementieren. Meine Version finde ich lesbarer. Da Fälle getrennt und Rückgabewerte explizit angegeben. Ich schätze aber, dass beide Versionen gleich schnell sind. Moderne Compiler optimieren da sehr viel weg.

Answer 3

Aber das kann bei einer 64-Bit-Zahl schon sehr lange dauern.

Hm. Wie sieht denn die Binärdarstellung einer Zweierpotenz aus? Wenn du das weißt sollte die Abfrage recht schnell gehen.

Frag dich weiterhin wie die Binärdarstellung ausschaut, wenn wir von der Zweierpotenz 1 abziehen.

Was passiert, wenn wir beide Zahlen mit einem Binären UND verknüpfen. Was kommt dann heraus. Wäre das auch bei Zahlen so, die keiner Zweierpotenzen sind?