Hi,

es handelt sich bei Integern um eine Zweierpotenz, wenn die Anzahl an Bits, die in der Zahl gesetzt sind, gerade gleich 1 ist.

Wie zählt man nun am besten Bits? Da gibt es einen schönen Trick: MIT HAKMEM (Unter dem Stichwort finden sich auch etliche andere Seiten mit Google)

Da man in PHP nicht direkt Oktalzahlen schreiben kann, funktioniert der dort angegebene C-Code natürlich nicht 1:1. Allerdings kann man die Oktalzahlen einfach in Hexadezimalzahlen umschreiben und dann funktioniert der Algorithmus genauso. Hinzu kommt allerdings die Schwierigkeit, dass PHP Integer grundsätzlich nur mit Vorzeichen unterstützt und damit maximal bis 31 Bit auf 32 Bit-Systemen funktioniert und 62 Bit auf 64 Bit-Systemen. Bei 32 Bit ist das kein Problem, da PHP auf Grund des Vorzeichens beim ersten Bit sowieso Probleme macht, bei 64 Bit muss das 63te Bit noch manuell nachgezogen werden (oder man wandelt den Algorithmus komplett ab, dass er mit Blöcken von 4 Bits und nicht mehr 3 Bits arbeitet).

Ich habe Dir mal den Algorithmus in PHP implementiert sowohl für 32 Bit-Systeme als auch 64 Bit-Systeme. Über PHP_INT_SIZE sollte er automatisch erkennen, welche Architektur das Betriebssystem, auf dem das Script ausgeführt wird, besitzt.

<?php  
  
/**  
 * Anzahl an Bits zählen  
 *  
 * Diese Funktion zählt die Anzahl an Bits in einer Zahl.  
 * Verwendet wird die MIT HAKMEM Methode, die auch unter  
 * http://www.cl.cam.ac.uk/~am21/hakmemc.html zu finden ist.  
 * Für 64bit-Zahlen wurde diese Methode generalisiert.  
 */  
if (PHP_INT_SIZE == 8) {  
  function countBits ($n) {  
    $upper = ($n & 0x4000000000000000) >> 62;  
    $n = $n & 0x3FFFFFFFFFFFFFFF;  
    $count = $n - (($n >> 1) & 0x36db6db6db6db6db) - (($n >> 2) & 0x1249249249249249);  
    return (($count + ($count >> 3)) & 0x31c71c71c71c71c7) % 63 + $upper;  
  }  
} else {  
  function countBits ($n) {  
    $count = $n - (($n >> 1) & 0xDB6DB6DB) - (($n >> 2) & 0x49249249);  
    return (($count + ($count >> 3)) & 0xC71C71C7) % 63;  
  }  
}  
  
?>

Wenn Du nun wissen willst, ob eine Zahl eine Zweierpotenz ist, kannst Du einfach prüfen, ob die Bit-Zähl-Funktion 1 zurückgibt:

$istZweierPotenz = countBits ($zahl) == 1;

Das funktioniert natürlich nur, wenn die Zweierpotenz sich noch im Wertebereich eines Integers bewegt (also mit 31 Bit oder 63 Bit darstellbar). Wenn sie nur noch durch eine Gleitkommazahl darstellbar ist, dann bleibt Dir wohl wirklich nichts anderes, als den Logarithmus zu ziehen und zu prüfen, ob er eine Ganzzahl ist oder (auf Grund der Gleitkommagenauigkeit) hinreichend nahe an eine Ganzzahl herankommt.

Viele Grüße,
Christian