Nächste Zweierpotenz berechnen

[Don P]

Hallo,

Die Dikussion um das beste Verfahren, die nächste größere Zweierpotenz für eine Zahl zu ermitteln, die keine Potenz von 2 ist, hat mich zu weiteren Experimenten angeregt.

Obwohl man mit dem einfachen Test (n-1)&n == 0 schnell ermitteln kann, ob n eine Potenz von 2 ist, war das leider wenig hilfreich zur Entwicklung eines schnellen Algorithmus', der ggf. nächst größere Zweierpotenz liefert.

Længlich hat gemessen, dass sein Algorithmus (PHP) um einiges schneller ist als meiner. Seiner braucht immer gerade so viele Schleifendurchläufe, wie die Zahl Binärstellen hat. Hier ist er in JavaScript:

  
var leanglich = function(zahl){        // Ermittelt die nächste Zweierpotenz nach Længlich.  
  
    var 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  
    }  
    return potenz;  
}

Und hier meiner:

  
var donP = function(zahl) {            // Ermittelt die nächste Zweierpotenz nach Don P.  
  
  if (!((zahl - 1) & zahl)) { return zahl; }  // Für Zweierpotenzen gilt: (n-1)&n === 0  
  
  var shr = 1;                                // Anzahl Rechts-Shifts bis Zweierpotenz erreicht  
  
  while ((zahl - 1) & zahl) {                 // Solange keine Zweierpotenz erreicht ist:  
  
    zahl >>= 1;                               //  Verschiebung um 1 nach rechts,  
    shr++;                                    //  Anzahl Verschiebungen merken.  
  }  
  
  return zahl << shr;                         // Enprechend wieder zurückschieben.  
}

Obwohl hier oft weniger Schleifendurchläufe nötig sind, im Idealfall gar keiner, ist dieser Code um die Hälfte langsamer, wohl hauptsächlich wegen der vielen Berechnungen von (n-1)&n.

Hier nochmal Længlichs Messergebnisse (PHP) für 5 mal 60000 Berechnungen in sec:

1. Don P: 0.44359087944
   Længlich: 0.278346061707
2. Don P: 0.409577131271
   Længlich: 0.289813995361
3. Don P: 0.392857074738
   Længlich: 0.295516967773
4. Don P: 0.398221969604
   Længlich: 0.284239053726
5. Don P: 0.409832954407
   Længlich: 0.280338048935

Wie ich herausfand, gibt es aber einen noch schnelleren Weg (jedenfalls in JavaScript): Man bestimmt das höchste gesetzte Bit einer Zahl mit Hilfe eines geeigneten Näherungsverfahrens, das stets nur wenige Iterationen braucht:

  
var newton = function(zahl) {          // Ermittelt die nächste Zweierpotenz durch Näherungsverfahren.  
  
  var step = 32,                       // Schrittweite in Bits für nächste zu testende Zweierpotenz  
      test = 1 << 62;                  // Unsere größte zu testende Zweierpotenz sei 2^30  
  
  while (step && test>zahl) {          // während Schrittweite>0 und Testzahl ist größer  
  
    step >>= 1;                        //  Schrittweite halbieren,  
    test >>= step;                     //  mit nächst kleinerer Testzahl weitermachen.  
  
    while (step && test<zahl) {        //  während Schrittweite>0 und Testzahl ist kleiner  
  
      step >>= 1;                      //   Schrittweite halbieren,  
      test <<= step;                   //   mit nächst gößerer Testzahl weitermachen.  
    }  
  }  
  
  if (test<zahl) { return test << 1; } // Zahl ist keine Zweierpotenz => nächst größere zurückgeben  
  return test;                         // Zahl ist Zweierpotenz => diese zurückgeben  
}  

Hier ein paar typische Messergebnisse für jeweils 60000 Berechnungen (JavaScript) in ms:

1. 60000 Zahlen 1...60001
   Don P: 500
   Newton: 344
   Længlich: 375

2. 60000 Zahlen 89940000...90000000
   Don P: 781
   Newton: 344
   Længlich: 563

3. 60000 Zahlen 1073681823...1073741823
   Don P: 859
   Newton: 329
   Længlich: 610

Wie man sieht, ist der Geschwindigkeitsvorteil ist umso deutlicher, je größer die Zahlen werden. Das war zu erwarten, weil die Anzahl der Schleifendurchläufe bei den bisherigen Lösungen linear mit den Testzahlen steigt, während es beim Näherungsverfahren immer nur max. 6 Iterationen sind.

Gruß, Don P