Jetzt aber hoffentlich die Lösung...

[Don P]

Hallo,

Muss noch erwähnen, dass ich das nur theoretisch (rein mathematisch) ausprobiert habe, nicht wirklich in PHP.

Und die Aufgabe war ja eigentlich, falls nötig die nächst höhere Zweierpotenz zu ermitteln.

Das geht dann etwa so:

  
function naechsteZweierPotenz( $n ) {  
  
  if ( (($n-1)&$n) == 0 ) return $n;  
  
  $p = 1;  
  while ( (($n-1)&$n) != 0 ) {  
  
    $n >>= 1;  
    $p++;  
  }  
  
  return $n << $p;  
}

Allerdings weiß ich nicht genau, wie PHP shiftet. Das Beispiel geht davon aus, dass z.B. (01101 >> 1) == 0110 gilt, d.h. ein einfaches logisches Shift, wobei das kleinste Bit einfach rechts rausgeschoben, d.h. verworfen wird. Für ungerade Zahlen entspricht das nicht einer Division durch 2.

Möglicherweise shiftet PHP aber anders, und nicht alle Betriebssysteme verwalten die Bits in derselben Reihenfolge :-(.

Im Zweifel könnte man die Funktion ohne Shiften so notieren:

  
function naechsteZweierPotenz( $n ) {  
  
  if ( !(($n-1)&$n) ) return $n;  
  
  $p = 1;  
  while ( ($n-1) & $n ) {  
  
    if ($n & 1) $n--;  
    $n /= 2;  
    $p++;  
  }  
  
  return $n * pow( 2, $p );  
}

In der Schleife wird $n jeweils erst zur geraden Zahl gemacht (also das kleinste Bit zu 0) und dann normal durch 2 dividiert (statt  shift right). Schließlich auch normal potenziert (statt  shift left).

Die Funktion braucht für eine Zahl n = 2 hoch x nur maximal x-1 Schleifendurchläufe. Natürlich sollte x nicht größer als 31 werden auf einem 32Bit-System, und negative Zahlen sind auch nicht vorgesehen...

Mit etwas weniger Code, dafür wohl im Schnitt auch ein bisschen langsamer:

  
function naechsteZweierPotenz( $n ) {  
  
  if ( !(($n-1)&$n) ) return $n;  
  
  $p = 2;  
  while ( $p < $n) ) { $p *= 2; }  
  return $p;  
}

Wie gesagt, alles ungetestet. Sollte aber wesentlich schneller sein als Logarithmieren oder Bits zählen.

Wenn es funktioniert, würde ich mich freuen, davon zu lesen. Natürlich auch wenn es falsch ist oder Schönheitsfehler hat. Das sind nämlich meine ersten Versuche in PHP. Soweit auch nur Trockenübungen. Also seid gnädig oder applaudiert ;-))

Gruß, Don P