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

[Længlich]

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