Zahl auf Zweierpotenz prüfen 👍 👎

Für manche Algorithmen bestehen Optimierungsansätze, wenn eine zu untersuchende Zahl eine Zweierpotenz ist. Daher möchte ich mit diesem Beitrag aufzeigen, wie sich diese Problemstellung möglichst effizient lösen lässt.

Naive Ansätze arbeiten mit Schleifen und prüfen schrittweise alle in Frage kommenden Zweierpotenzen – es ist leicht einzusehen, dass dieses Vorgehen insbesondere für größere Zahlen eher mäßig effizient ist. Alternativ könnte man auf die Idee kommen, das Problem mit Logarithmen zu lösen – hier kann es jedoch zu Rundungsproblemen kommen. Wir sollten uns daher die Struktur entsprechender Zahlen einmal genauer ansehen:
Zweierpotenzen
010203040506
                  Dualzahl     Dezimalzahl--------------------------------------------       20               1            1       21              10            2       22             100            4       23            1000            8
Offensichtlich ist bei einer Zweierpotenz 2n demnach das (n + 1)-te Bit auf 1 gesetzt und alle ggf. nachfolgenden Stellen besitzen den Wert 0 – was kaum eine Überraschung darstellen sollte. Wir müssen nun jedoch nicht jedes Bit einzeln prüfen, ob die Zahl auf dieses "Muster" passt, sondern können uns das Bitmuster der Zahl 2n – 1 zu Nutze machen:
Voränger von Zweierpotenzen
010203040506
                  Dualzahl     2n – 1 (dual)--------------------------------------------       20               1            0       21              10           01       22             100          011       23            1000         0111
Wie selbstverständlich zu erwarten war, muss der Vorgänger ein inverses Bitmuster besitzen. Dies hilft uns insofern weiter, als dass wir diese beiden Zahlen mit einem bitweisen UND verknüpfen und auf Gleichheit mit 0 prüfen können, was bei Zweierpotenzen zutreffen muss.

In C# könnte die Implementierung beispielsweise wie folgt aussehen:
Zahl auf Zweierpotenz prüfen (Basis)
010203
public static bool IsPowerOfTwo(uint number) {    return ((number & (number – 1)) == 0);}
Dieses Vorgehen liefert jedoch auch für die Zahl 0 den Wert true zurück. Wir prüfen diesen Fall daher separat:
Zahl auf Zweierpotenz prüfen (Erweiterung)
01020304050607
public static bool IsPowerOfTwo(uint number) {    return (        (number != 0)          &&        ((number & (number – 1)) == 0)    );}


Projektverweise

Kategorien / Archiv  |  Übersicht RSS-Feed

Schlagworte

Suche