mike: Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)?

Hallo,

ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...

Wenn nicht, soll er die Zahl zur nächst höheren Zweierpotenz machen.

Ich habe es jetzt erstmal mit dem Logarithmus der Zahl zur Basis 2 versucht, und teste dann, ob das Ergebnis eine ganze Zahl ist.

$zahl = 3;

while(!is_int(log($zahl, 2))) {
 $zahl++;
}
echo $zahl;

Hier ist nur das Problem, dass der log immer ein "float"-Ergebnis zurückgibt, und ich deswegen nicht auf "integer" prüfen kann.

Ich bin dankbar für jeden Tipp, evtl. gibt's ja auch noch ne andere Lösung...

Vielen Dank,

Mike

  1. teile durch zwei und runde ab.
    multipliziere das ergebnis mit 2 und schau nach ob die zahl vorher = der zahl nachher ist.
    also:
    function test(zahl){
     return (Math.floor(zahl/2)*2)==zahl)?true:false;
    }

    1. verzeihung: anfängerfehler: ich hab das php überlesen.
      ich kenne mich mit php nicht aus, aber mein system ist hoffendlich übertragbar?

      1. verzeihung: anfängerfehler: ich hab das php überlesen.
        ich kenne mich mit php nicht aus, aber mein system ist hoffendlich übertragbar?

        fuktioniert wohl irgendwie nicht... ich weiß grad auch nicht warum. Ich bekomme immer "false".

        Jedenfalls danke für deinen Ansatz...

        Mike

        1. Ich kann mit dem Ansatz gerade nicht viel anfangen:

          Bsp: Zahl ist 10   (also keine Zweierpotenz => "false")

          12/2 = 6
              6*2 = 12
              abrunden: 12    => ist gleich der anfangszahl, also ?true?

          1. OK, jetzt hab ich's kapiert:

            Wir haben aneinander vorbeigeredet: Ich muss nicht auf gerade Zahlen prüfen, sondern auf Zahlen wie 2^n also 2,4,8,16,32,64,128,256,...

            Weiß niemand eine Lösung?

            Mike

            1. Weiß niemand eine Lösung?

              ja,
              steht ein bissel weiter oben ...

              Gruss Norbert

              1. Weiß niemand eine Lösung?
                ja,
                steht ein bissel weiter oben ...

                Gruss Norbert

                Oh, mann; Brett vorm Kopf ^^

                Funktioniert Super! Vielen Dank!

                Schönen Abend, Mike

        2. Hallo Mike,

          <?php  
          $xx = 123456789;  /* Deliquent */  
          echo ceil(log($xx, 2));  
          ?>
          

          Ceil - liefert die naechste ganze Zahl die groesser oder gleich dem Parameter ist.

          Gruss Norbert

    2. Moin Moin!

      teile durch zwei und runde ab.
      multipliziere das ergebnis mit 2 und schau nach ob die zahl vorher = der zahl nachher ist.

      Damit testest Du nur, ob die Zahl gerade oder ungerade ist. Und für Nicht-Integer-Zahlen wird das Ergebnis mit diesem Algorithmus immer "ungerade" lauten.

      Alexander

      --
      Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so".
  2. Hallo,

    Zweierpotenzen haben ja die Eigenschaft, in Binärdarstellung genau eine 1 aufzuweisen (das höchste Bit).

    Es sei m die in PHP größtmögliche Zahl, die in Binärdarstellung nur Einsen aufweist, welche das auch immer sein mag ;-), also Binärzahl wie 11111111...

    Dann liefert IMHO der Vergleich

    ~(n^m) == n

    true, falls n eine Zweierpotenz ist, andernfalls false.

    Gruß, Don P

    1. Hallo,

      Diese größtmögliche Zahl kann man ja evtl. durch negieren der 0 erhalten. Der Vergleich

      ~(n^~0) == n

      müsste es dann eigentlich tun, jedenfalls für positive n, d.h. unsigned Integer, wenn ich nicht irre...

      Gruß, Don P

    2. Hallo Don,

      Zweierpotenzen haben ja die Eigenschaft, in Binärdarstellung genau eine 1 aufzuweisen (das höchste Bit).

      auf diesem Trip war ich auch schon; mir wollte nur auf die Schnelle noch kein Algorithmus einfallen, der genau das herausbekommt. Gut, wenn ich den Zahlenbereich kenne und weiß, dass die Zahl intern mit maximal k Bits dargestellt wird, kann ich k-mal hergehen und das LSB prüfen, dann die Zahl um ein Bit rechtsschieben und erneut prüfen. Wenn ich damit mehr als ein gesetztes Bit finde, ist es keine Zweierpotenz.

      Es sei m die in PHP größtmögliche Zahl, die in Binärdarstellung nur Einsen aufweist, welche das auch immer sein mag ;-), also Binärzahl wie 11111111...

      You are on the wooden way. ;-)

      Dann liefert IMHO der Vergleich
      ~(n^m) == n
      true, falls n eine Zweierpotenz ist, andernfalls false.

      Nein, dieser Ausdruck liefert dann immer true. Denn die XOR-Verknüpfung mit dem vorzeichenlos größten darstellbaren Wert ist, banal ausgedrückt, eine bitweise Negation. Mit dem Operator ~ negierst du den Ausdruck ein zweites Mal und bekommst so wieder n heraus. qed.

      So long,
       Martin

      --
      Die letzten Worte des stotternden Beifahrers:
      Frei... frei... frei... freilich kommt da was!!
      1. Hallo,

        Dann liefert IMHO der Vergleich
        ~(n^m) == n
        true, falls n eine Zweierpotenz ist, andernfalls false.

        Nein, dieser Ausdruck liefert dann immer true. Denn die XOR-Verknüpfung mit dem vorzeichenlos größten darstellbaren Wert ist, banal ausgedrückt, eine bitweise Negation.

        Meinst du wirklich? XOR liefert doch nur dann 1, wenn die Bits verschieden sind, sonst 0. Also z.B. so:

        n = 0100 (Zweierpotenz)
        ~0000 sei 1111 (also unsere größte Zahl)

        somit:
        n XOR m = 1011
        und dann negiert:
        0100
        was wieder unsere Ausgangszahl ist.

        Wenn n keine Zweierpotenz ist, kommrn wir aber nicht mehr zur Ausgangszahl zurück, q.e.d.

        Gruß, Don P

        1. Hi,

          Mal eine kleine Änderung:

          n = 0111 (keine Zweierpotenz)
          ~0000 sei 1111 (also unsere größte Zahl)

          somit:
          n XOR m = 1000

          0111
          xor 1111
          --------
              1000

          und dann negiert:
          0111

          In diesem Beispiel auch wieder die Ausgangszahl

          Wenn n keine Zweierpotenz ist, kommen wir aber nicht mehr zur Ausgangszahl zurück, q.e.d.

          Eben schon.

          mfG,
          steckl

          1. Hallo,

            Shit... hatte es eigentlich ausprobiert, und jetzt klappt´s nicht mehr. Weiß auch nicht, wo ich da hingedacht habe. Man sollte so spät die grauen Zellen lieber ausruhen lassen... ;-)

            Gruß, Don P

  3. 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

    1. Hallo,

      Andere Variante:

      Man subtrahiert einfach 1 von der Ausgangszahl und macht dann eine logische Und-Verknüpfung mit derselben. Wenn das Ergebnis 0 ist, ist die Ausgangszahl eine Zweierpotenz (leider incl. 2 hoch 0 = 1), sonst nicht.

      Das ergibt sich unmittelbar aus der Tatsache, dass rechts des höchsten Bit nur noch Nullen stehen (bei Zweierpotenzen). Durch Subtraktion von 1 werden diese alle zu 1, während das vorher höchste Bit zu 0 wird, was durch die Und-Verknüpfung mit der Ausgangszahl zu insgesamt 0 führen muss.

      Andererseits führt die Subtraktion von 1 nicht zu einer Änderung des höchsten Bit, wenn die Ausgangszahl keine Zweierpotenz ist, so dass die anschließende Und-Verknüfung auch nicht zu insgesamt 0 führen kann.

      Die Vergleich lautet also:

      (n-1)&n == 0

      Er liefert true für Zweierpotenzen n > 1, sonst false.

      Das scheint jetzt nun wirklich zu funktionieren. Habe es in vielen Varianten ausprobiert und es ergibt sich schon rein durch die Logik.

      Gruß, Don P

      1. 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

    2. Hi,

      Wie zählt man nun am besten Bits?

      substr_count(decbin($integer), '1')

      MfG ChrisB

      1. Hallo Chris,

        Wie zählt man nun am besten Bits?

        substr_count(decbin($integer), '1')

        Och, das wäre doch langweilig. ;-)

        Viele Grüße,
        Christian

    3. Tach.

      Wie zählt man nun am besten Bits? Da gibt es einen schönen Trick: MIT HAKMEM

      Wow, das ist wirklich sehr clever.

      Da man in PHP nicht direkt Oktalzahlen schreiben kann, funktioniert der dort angegebene C-Code natürlich nicht 1:1.

      Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...

      --
      Once is a mistake, twice is Jazz.
      1. Hallo,

        Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...

        Mit den Oktalzahlen in dem Algorithmus hat's nicht funktioniert (PHP hat sie als Dezimalzahlen interpretiert), also habe sie einfach in Hex umgerechnet, damit's keine Probleme gibt. Ich VERMUTE mal, dass PHP beim Umwandeln Probleme macht, wenn die Oktalzahl als Dezimal gelesen nicht mehr in die 32 Bits reinpasst...

        Viele Grüße,
        Christian

        1. Tach.

          Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...

          Mit den Oktalzahlen in dem Algorithmus hat's nicht funktioniert (PHP hat sie als Dezimalzahlen interpretiert), also habe sie einfach in Hex umgerechnet, damit's keine Probleme gibt. Ich VERMUTE mal, dass PHP beim Umwandeln Probleme macht, wenn die Oktalzahl als Dezimal gelesen nicht mehr in die 32 Bits reinpasst...

          Ja, es scheint tatsächlich an der Größe der Zahl zu liegen. Auf meinem 32-Bit-System ist oberhalb von 013333333333 Schluß mit Oktalzahlen; danach wird's, wie bei Dir, eine Dezimalzahl. Dein erstes Posting hatte ich erst so mißverstanden, daß PHP generell keine Oktalnotation beherrscht.

          Was ich an Deiner Implementation übrigens interessant finde, ist, daß sie funktioniert, obwohl PHP auf 32-Bit-Systemen die Zahl 0xDB6DB6DB laut var_dump() schon als Float darstellt und damit trotzdem die VerUNDund nicht verbockt ... Gibt es da intern nochmal eine Konvertierung in eine Ganzzahl?

          --
          Once is a mistake, twice is Jazz.
          1. Hallo,

            Was ich an Deiner Implementation übrigens interessant finde, ist, daß sie funktioniert, obwohl PHP auf 32-Bit-Systemen die Zahl 0xDB6DB6DB laut var_dump() schon als Float darstellt und damit trotzdem die VerUNDund nicht verbockt ... Gibt es da intern nochmal eine Konvertierung in eine Ganzzahl?

            Wenn man Zahlen mit Bitoperatoren verknüpft werden sie in Integer konvertiert - und wenn sie direkt bei Bitoperatoren dabeistehen als konstante Zahlen im Script, dann werden sie gar nicht erst in Float gewandelt.

            Beispiel:

            <?php  
            var_dump (0xDB6DB6DB);  
            $x = 0xDB6DB6DB;  
            var_dump ($x);  
            var_dump (0xDB6DB6DB | 0x00);  
            var_dump ($x | 0x00);  
            $y = 0xDB6DB6DB | 0x00;  
            var_dump ($y);  
            ?>
            

            Ergibt auf 32bit-Systemen:

            float(3681400539)
            float(3681400539)
            int(-613566757)
            int(-613566757)
            int(-613566757)

            (Das Minuszeichen kommt daher, dass die Zahl größer ist, als die größte mit PHP darstellbare vorzeichenlose Zahl)

            Viele Grüße,
            Christian

            1. Tach.

              Wenn man Zahlen mit Bitoperatoren verknüpft werden sie in Integer konvertiert - und wenn sie direkt bei Bitoperatoren dabeistehen als konstante Zahlen im Script, dann werden sie gar nicht erst in Float gewandelt.

              Ah, interessant. Darauf, letzteres mal zu überprüfen, hätte ich eigentlich selber kommen können, LOL. Danke für die Info.

              --
              Once is a mistake, twice is Jazz.
  4. Voghdzuyin!

    ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...

    Wenn nicht, soll er die Zahl zur nächst höheren Zweierpotenz machen.

    Zur Prüfung gab's ja schon einige Antworten. Aber eigentlich brauchst Du die doch gar nicht, oder? Du willst immer die kleinste Zweierpotenz haben, die größergleich Deine $zahl ist:

      
    if ($zahl < 1)  
    {  
        echo('Was immer Du in diesem Fall haben willst');  
    }  
    else  
    {  
        $potenz = 1; // Wir fangen mit der kleinsten an  
        while ($zahl > $potenz) // Solange sie noch zu klein ist...  
        {  
            $potenz <<= 1; // ... versuchen wir die nächsthöhere  
        }  
        echo($potenz);  
    }  
    
    

    Viele Grüße vom Længlich

    1. Nachtrag:
      Wenn die $zahl größer ist als die größte darstellbare Zweierpotenz, dann gibt's bei meinem Ansatz einen Überlauf. Das muß auch im Vorfeld abgefangen werden.

      Viele Grüße vom Længlich

    2. Hallo Længlich,

      Voghdzuyin!

      Wieso denn Bahnhof? ;-)

      Anscheinend liest der OP nicht mehr mit, er war ja schon gestern mit ceil(log($xx, 2)) als Test auf Zweierpotenzen zufrieden. Das hält uns aber nicht davon ab, noch bessere Lösungen zu finden, gelle :-)

      Dein Ansatz ist sicher bis jetzt der einfachste.
      Wenn es auf Performance ankommt, ist

      function naechsteZweierPotenz( $n ) {

      if ( !(($n-1)&$n) ) return $n;

      $p = 1;
        while ( ($n-1)&$n ) {

      $n >>= 1;
          $p++;
        }

      return $n << $p;
      }

        
      aber wohl kaum zu schlagen. Habe das in JavaScript umgesetzt und ausprobiert: Funktioniert einwandfrei. Für PHP habe ich jetzt leider keine Testmöglichkeit.  
        
      Es gelten in etwa die gleichen Einschränkungen:  
      - Die übergebene Zahl muss Integer und >0 sein  
      - Die nächsthöhere Zweierpotenz muss darstellbar sein  
        
      Gruß, Don P
      
      1. Aloha!

        Voghdzuyin!

        Wieso denn Bahnhof? ;-)

        Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)

        Anscheinend liest der OP nicht mehr mit, er war ja schon gestern mit ceil(log($xx, 2)) als Test auf Zweierpotenzen zufrieden. Das hält uns aber nicht davon ab, noch bessere Lösungen zu finden, gelle :-)

        Jetzt macht's ja erst richtig Spaß! ;-) Und wir wollen doch am Ende die beste Lösung im Archiv haben. <offtopic>Das Archiv ist überhaupt super: Seit ca. 3 Jahren finde ich so zuverlässig Antworten auf alle meine Fragen, daß ich noch nie einen eigenen Thread starten mußte. :-)</offtopic>

        Dein Ansatz ist sicher bis jetzt der einfachste.

        Das war das Ziel.

        Wenn es auf Performance ankommt, ist [...]
        aber wohl kaum zu schlagen. Habe das in JavaScript umgesetzt und ausprobiert: Funktioniert einwandfrei. Für PHP habe ich jetzt leider keine Testmöglichkeit.

        Ich widerspreche nur ungern, aber die Aussage kam mir komisch vor. Meine Schleife enthält nur einen Vergleich, einen Bitshift und eine Zuweisung. Deine enthält eine Subtraktion, eine Addition, ein bitweises Und, eine Negation, einen Bitshift und zwei Zuweisungen. Beide brauchen, wenn ich das richtig sehe, log₂($n) Durchläufe.

        Also habe ich mal in PHP die Zeiten gemessen, und zwar wie folgt: In einer for-Schleife wird $n von 1 bis 60000 hochgezählt (die 60000 ist Willkür; ich habe es auch mit 20000 und mit 15 probiert) und mit jedem $n die Funktion aufgerufen. Das Ergebnis wird $v zugewiesen, aber nicht weiter verarbeitet.
        Ergebnisse von 5 Script-Aufrufen (in sec):
        Don P: 0.44359087944
        Længlich: 0.278346061707
        Don P: 0.409577131271
        Længlich: 0.289813995361
        Don P: 0.392857074738
        Længlich: 0.295516967773
        Don P: 0.398221969604
        Længlich: 0.284239053726
        Don P: 0.409832954407
        Længlich: 0.280338048935

        Dann habe ich noch versucht, Deine Prüfung (if (!(($n - 1) & $n)) return $n;) in meine Funktion einzubauen, um gelegentlich die Schleife ganz einzusparen. Davon wurde es interessanterweise aber auch langsamer (lag in der Größenordnung 0.30 bis 0.33).

        Hast Du in Javascript die Zeit gemessen? Sah das da anders aus?

        Viele Grüße vom Længlich

        1. Hallo Længlich,

          <offtopic>

          Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)

          Aha, und "Voghdzuyin!" wäre dann wohl klingonisch ;)

          Das Archiv ist überhaupt super: Seit ca. 3 Jahren finde ich so zuverlässig Antworten auf alle meine Fragen, daß ich noch nie einen eigenen Thread starten mußte. :-)

          Geht mir ähnlich :)

          </offtopic>

          Meine Schleife enthält nur einen Vergleich, einen Bitshift und eine Zuweisung. Deine enthält eine Subtraktion, eine Addition, ein bitweises Und, eine Negation, einen Bitshift und zwei Zuweisungen.

          Stimmt auffallend.

          Beide brauchen, wenn ich das richtig sehe, log₂($n) Durchläufe.

          Das nicht. Der Grund, warum ich meine Lösung für schneller gehalten habe, ist gerade, weil sie nicht für jedes n genau log₂ n Schleifendurchläufe braucht:
          Für Zweierpotenzen n braucht es gar keine Schleife, und für andere n nur gerade so viele, bis alle gesetzten Bits außer dem hochwertigsten nach rechts "rausgeshiftet" sind. Eine Zahl der Binärform 10...01 z.B. braucht nur einen einzigen Schleifendurchlauf und anschließend eine einzige Shift-Left-Operation. Die maximal nötige Anzahl Durchläufe ist zwar auch log₂ n, aber das tritt nur ein für solche Zahlen n, die die Binärform 11... aufweisen. Ich denke, dass meine Funktion gegenüber deiner umso besser abschneidet, je größer n wird. 1...60000 ist ja eher kleine Zahlen ;-)

          Ergebnisse von 5 Script-Aufrufen (in sec):

          Also 5 mal von 1...60000, macht insgesamt 300 000 Berechnungen in der angegebenen Gesamtzeit? Oder ist das jeweils der Durchschnitt für 60000 Berechnungen?

          Don P: 0.44359087944
          Længlich: 0.278346061707
          Don P: 0.409577131271
          Længlich: 0.289813995361
          Don P: 0.392857074738
          Længlich: 0.295516967773
          Don P: 0.398221969604
          Længlich: 0.284239053726
          Don P: 0.409832954407
          Længlich: 0.280338048935

          Wow, pfeilschnell. Das hat mich allerdings überrascht. Muss wohl in Zukunft wirklich mit meinen Schätzungen vorsichtiger sein. Etwas ähnliches ist mir hier nämlich schon einmal passiert. Erst große Töne gespuckt von wegen super Performance meines Codes, und dann eines Besseren belehrt worden, peinlich, peinlich...

          Dann habe ich noch versucht, Deine Prüfung (if (!(($n - 1) & $n)) return $n;) in meine Funktion einzubauen, um gelegentlich die Schleife ganz einzusparen. Davon wurde es interessanterweise aber auch langsamer (lag in der Größenordnung 0.30 bis 0.33).

          Das wundert mich inzwischen nicht mehr, denn die wenigen Fälle, wo der Delinquent zufällig eine Zweierpotenz ist und man etwas einsparen kann, fallen wohl kaum ins Gewicht gegenüber der riesigen Mehrheit der Fälle, wo das nicht der Fall ist. Diese zusätzliche Prüfung bremst also meistens nur aus.

          Hast Du in Javascript die Zeit gemessen? Sah das da anders aus?

          Nein, die Mühe und anschließende Schmach erspare ich mir lieber. Bitweise Operationen sind in JavaScript bekannterweise langsam, weil dabei intern noch Integer-Floatingpoint-Umwandlungen stattfinden müssen. Außerdem ist es unmöglich, Zeitmessungen für länger laufende Scripte in einem Browser zu machen, weil Browser dann zu Abstürzen neigen oder zumindest die Javascript-Ausführung unterbrechen, um den Benutzer zu fragen, ob er das Wahnsinns-Script wirklich weiter laufen lassen will. Vielleicht probiere ich es mal in einer anderen Anwendung, die solches Verhalten nicht zeigt...

          Danke jedenfalls für deine ernüchternden Messungen.

          Gruß, Don P

          1. Qapla'!

            <offtopic>

            Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)
            Aha, und "Voghdzuyin!" wäre dann wohl klingonisch ;)

            Nein, armenisch. »Qapla'!« ist klingonisch. ;-)

            </offtopic>

            [...]
            Das nicht. Der Grund, warum ich meine Lösung für schneller gehalten habe, ist gerade, weil sie nicht für jedes n genau log₂ n Schleifendurchläufe braucht:
            Für Zweierpotenzen n braucht es gar keine Schleife, und für andere n nur gerade so viele, bis alle gesetzten Bits außer dem hochwertigsten nach rechts "rausgeshiftet" sind. Eine Zahl der Binärform 10...01 z.B. braucht nur einen einzigen Schleifendurchlauf und anschließend eine einzige Shift-Left-Operation.

            Ah ja, hast recht. Das erkaufst Du Dir allerdings mit der wesentlich aufwendigeren Überprüfung.

            Die maximal nötige Anzahl Durchläufe ist zwar auch log₂ n, aber das tritt nur ein für solche Zahlen n, die die Binärform 11... aufweisen. Ich denke, dass meine Funktion gegenüber deiner umso besser abschneidet, je größer n wird. 1...60000 ist ja eher kleine Zahlen ;-)

            Die Zweierpotenzen werden allerdings bei höheren Zahlen immer seltener, so daß die Ersparnis immer unwahrscheinlicher wird. Also wieder testen. ;-)

            Ergebnisse von 5 Script-Aufrufen (in sec):
            Also 5 mal von 1...60000, macht insgesamt 300 000 Berechnungen in der angegebenen Gesamtzeit? Oder ist das jeweils der Durchschnitt für 60000 Berechnungen?

            Das Testscript sah so aus:

              
             $time = microtime(true);  
             for ($n = 1; $n < 60000; $n++)  
             {  
              $v = DonPAlgorithm($n);  
             }  
             echo("\nDon P: " . (microtime(true) - $time));  
             $time = microtime(true);  
             for ($n = 1; $n < 60000; $n++)  
             {  
              $v = LaenglichAlgorithm($n);  
             }  
             echo("\nLænglich: " . (microtime(true) - $time));  
            
            

            D.h. jeder unserer beiden Algorithmen läuft mit jeder Zahl von 1 bis 60000 genau einmal durch, und die gemessene Zeit ist diejenige, die für diese - wie mir jetzt gerade auffällt ;-) - 59999 Rechnungen gebraucht wurde. Das ganze habe ich fünfmal laufen lassen, damit wir uns ein Bild von den statistischen Schwankungen machen können.

            Und jetzt testen wir mal mit 1,2 Mio - 1 Rechnungen:
            Don P: 8.82406592369
            Længlich: 6.48715186119
            Don P: 8.70618391037
            Længlich: 6.52737307549
            Don P: 8.61320590973
            Længlich: 6.48604202271

            Meins ist immer noch schneller. 2,2 Mio - 1:
            Don P: 16.45282197
            Længlich: 12.4065210819

            Scheint sogar immer ungefähr das selbe Verhältnis zu bleiben. Noch höhere Zahlen möchte ich meinem Rechner jetzt nicht mehr zumuten, zumal wir uns ohnehin rasant auf den Timeout zubewegen. Man müßte wohl mit C oder noch besser mit Assembler weitermachen. ;-)

            Nein, die Mühe und anschließende Schmach erspare ich mir lieber.

            Wieso denn Schmach? Wir sind hier zusammen wissenschaftlich tätig! Ohne Dich wäre ich nie auf die Idee gekommen, das überhaupt zu messen, und jetzt finde ich es richtig interessant. ;-)

            Bitweise Operationen sind in JavaScript bekannterweise langsam, weil dabei intern noch Integer-Floatingpoint-Umwandlungen stattfinden müssen.

            Ja, solche Sachen beeinflussen das Ergebnis bestimmt sehr. Man könnte es auch noch mit dem Datentyp »Variant« in Visual Basic testen - der macht auch alles gewaltig langsamer. Theoretisch wäre wohl wirklich Assembler am besten.

            Viele Grüße vom Længlich

  5. Hallo,

    ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...

    Bei allen Zahlen, die eine Potenz von 2 sind, ist nur ein Bit gesetzt:

    00000010 = 2
    00000100 = 4
    00001000 = 8
    00010000 = 16
    00100000 = 32
    01000000 = 64
    10000000 = 128

    usw.

    Nur mal so als Denkanstoß ;-)

    Viele Grüße,
    Hotte