tag:forum.selfhtml.org,2005:/self Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? – SELFHTML-Forum 2007-12-07T19:07:45Z https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188745#m1188745 mike webmaster@judo-eichenau.de 2007-12-05T18:22:01Z 2007-12-05T18:22:01Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <p>ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...</p> <p>Wenn nicht, soll er die Zahl zur nächst höheren Zweierpotenz machen.</p> <p>Ich habe es jetzt erstmal mit dem Logarithmus der Zahl zur Basis 2 versucht, und teste dann, ob das Ergebnis eine ganze Zahl ist.</p> <p>$zahl = 3;</p> <p>while(!is_int(log($zahl, 2))) {<br>  $zahl++;<br> }<br> echo $zahl;</p> <p>Hier ist nur das Problem, dass der log immer ein "float"-Ergebnis zurückgibt, und ich deswegen nicht auf "integer" prüfen kann.</p> <p>Ich bin dankbar für jeden Tipp, evtl. gibt's ja auch noch ne andere Lösung...</p> <p>Vielen Dank,</p> <p>Mike</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188769#m1188769 flying sheep flying-sheep@web.de 2007-12-05T18:31:50Z 2007-12-05T18:31:50Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>teile durch zwei und runde ab.<br> multipliziere das ergebnis mit 2 und schau nach ob die zahl vorher = der zahl nachher ist.<br> also:<br> function test(zahl){<br>  return (Math.floor(zahl/2)*2)==zahl)?true:false;<br> }</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188763#m1188763 Don P 2007-12-05T19:45:43Z 2007-12-05T19:45:43Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <p>Zweierpotenzen haben ja die Eigenschaft, in Binärdarstellung genau eine 1 aufzuweisen (das höchste Bit).</p> <p>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...</p> <p>Dann liefert IMHO der Vergleich</p> <p>~(n^m) == n</p> <p>true, falls n eine Zweierpotenz ist, andernfalls false.</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188753#m1188753 Christian Seiler self@christian-seiler.de 2007-12-05T22:22:30Z 2007-12-05T22:22:30Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hi,</p> <p>es handelt sich bei Integern um eine Zweierpotenz, wenn die Anzahl an Bits, die in der Zahl gesetzt sind, gerade gleich 1 ist.</p> <p>Wie zählt man nun am besten Bits? Da gibt es einen schönen Trick: <a href="http://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/" rel="nofollow noopener noreferrer">MIT HAKMEM</a> (Unter dem Stichwort finden sich auch etliche andere Seiten mit Google)</p> <p>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).</p> <p>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.</p> <pre><code class="block language-php"><span class="token php language-php"><span class="token delimiter important"><?php</span> <span class="token comment">/** * 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. */</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token constant">PHP_INT_SIZE</span> <span class="token operator">==</span> <span class="token number">8</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">function</span> <span class="token function-definition function">countBits</span> <span class="token punctuation">(</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$upper</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">&</span> <span class="token number">0x4000000000000000</span><span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">62</span><span class="token punctuation">;</span> <span class="token variable">$n</span> <span class="token operator">=</span> <span class="token variable">$n</span> <span class="token operator">&</span> <span class="token number">0x3FFFFFFFFFFFFFFF</span><span class="token punctuation">;</span> <span class="token variable">$count</span> <span class="token operator">=</span> <span class="token variable">$n</span> <span class="token operator">-</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0x36db6db6db6db6db</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">>></span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0x1249249249249249</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$count</span> <span class="token operator">+</span> <span class="token punctuation">(</span><span class="token variable">$count</span> <span class="token operator">>></span> <span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0x31c71c71c71c71c7</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">63</span> <span class="token operator">+</span> <span class="token variable">$upper</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token keyword">function</span> <span class="token function-definition function">countBits</span> <span class="token punctuation">(</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$count</span> <span class="token operator">=</span> <span class="token variable">$n</span> <span class="token operator">-</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0xDB6DB6DB</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">>></span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0x49249249</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$count</span> <span class="token operator">+</span> <span class="token punctuation">(</span><span class="token variable">$count</span> <span class="token operator">>></span> <span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token number">0xC71C71C7</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">63</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token delimiter important">?></span></span> </code></pre> <p>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:</p> <p><code class="language-php"><span class="token variable">$istZweierPotenz</span> <span class="token operator">=</span> <span class="token function">countBits</span> <span class="token punctuation">(</span><span class="token variable">$zahl</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">;</span></code></p> <p>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.</p> <p>Viele Grüße,<br> Christian</p> <div class="signature">-- <br> <a href="http://del.icio.us/chris_se/servertipps" rel="nofollow noopener noreferrer">Mein "Weblog"</a> [<a href="http://del.icio.us/rss/chris_se/servertipps" rel="nofollow noopener noreferrer">RSS</a>] </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188747#m1188747 Længlich http://www.grinningbit.com 2007-12-06T10:44:11Z 2007-12-06T10:44:11Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Voghdzuyin!</p> <blockquote> <p>ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...</p> <p>Wenn nicht, soll er die Zahl zur nächst höheren Zweierpotenz machen.</p> </blockquote> <p>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:</p> <pre><code class="block language-php"> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token variable">$zahl</span> <span class="token operator"><</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">echo</span><span class="token punctuation">(</span><span class="token string single-quoted-string">'Was immer Du in diesem Fall haben willst'</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token variable">$potenz</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// Wir fangen mit der kleinsten an </span> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token variable">$zahl</span> <span class="token operator">></span> <span class="token variable">$potenz</span><span class="token punctuation">)</span> <span class="token comment">// Solange sie noch zu klein ist... </span> <span class="token punctuation">{</span> <span class="token variable">$potenz</span> <span class="token operator"><<</span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// ... versuchen wir die nächsthöhere </span> <span class="token punctuation">}</span> <span class="token keyword">echo</span><span class="token punctuation">(</span><span class="token variable">$potenz</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> </code></pre> <p>Viele Grüße vom Længlich</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188746#m1188746 Horst 2007-12-07T14:42:38Z 2007-12-07T14:42:38Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <blockquote> <p>ich will prüfen, ob eine Variable eine Zweierpotenz (2^n) ist, oder nicht...</p> </blockquote> <p>Bei allen Zahlen, die eine Potenz von 2 sind, ist nur ein Bit gesetzt:</p> <p>00000010 = 2<br> 00000100 = 4<br> 00001000 = 8<br> 00010000 = 16<br> 00100000 = 32<br> 01000000 = 64<br> 10000000 = 128</p> <p>usw.</p> <p>Nur mal so als Denkanstoß ;-)</p> <p>Viele Grüße,<br> Hotte</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188752#m1188752 Længlich http://www.grinningbit.com 2007-12-06T11:08:13Z 2007-12-06T11:08:13Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Nachtrag:<br> 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.</p> <p>Viele Grüße vom Længlich</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188748#m1188748 Don P 2007-12-06T12:04:41Z 2007-12-06T12:04:41Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo Længlich,</p> <blockquote> <p>Voghdzuyin!</p> </blockquote> <p>Wieso denn Bahnhof? ;-)</p> <p>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 :-)</p> <p>Dein Ansatz ist sicher bis jetzt der einfachste.<br> Wenn es auf Performance ankommt, ist</p> <blockquote> <pre><code class="block language-php"></code></pre> </blockquote> <blockquote> <p>function naechsteZweierPotenz( $n ) {</p> <p>if ( !(($n-1)&$n) ) return $n;</p> <p>$p = 1;<br>   while ( ($n-1)&$n ) {</p> <p>$n >>= 1;<br>     $p++;<br>   }</p> <p>return $n << $p;<br> }</p> </blockquote> <pre><code class="block"> 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 </code></pre> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188749#m1188749 Længlich http://www.grinningbit.com 2007-12-06T19:05:31Z 2007-12-06T19:05:31Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Aloha!</p> <blockquote> <blockquote> <p>Voghdzuyin!</p> </blockquote> <p>Wieso denn Bahnhof? ;-)</p> </blockquote> <p>Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)</p> <blockquote> <p>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 :-)</p> </blockquote> <p>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></p> <blockquote> <p>Dein Ansatz ist sicher bis jetzt der einfachste.</p> </blockquote> <p>Das war das Ziel.</p> <blockquote> <p>Wenn es auf Performance ankommt, ist [...]<br> aber wohl kaum zu schlagen. Habe das in JavaScript umgesetzt und ausprobiert: Funktioniert einwandfrei. Für PHP habe ich jetzt leider keine Testmöglichkeit.</p> </blockquote> <p>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.</p> <p>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.<br> Ergebnisse von 5 Script-Aufrufen (in sec):<br> Don P: 0.44359087944<br> Længlich: 0.278346061707<br> Don P: 0.409577131271<br> Længlich: 0.289813995361<br> Don P: 0.392857074738<br> Længlich: 0.295516967773<br> Don P: 0.398221969604<br> Længlich: 0.284239053726<br> Don P: 0.409832954407<br> Længlich: 0.280338048935</p> <p>Dann habe ich noch versucht, Deine Prüfung (<code class="language-php"><span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token variable">$n</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token variable">$n</span><span class="token punctuation">;</span></code>) 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).</p> <p>Hast Du in Javascript die Zeit gemessen? Sah das da anders aus?</p> <p>Viele Grüße vom Længlich</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188750#m1188750 Don P 2007-12-07T14:23:18Z 2007-12-07T14:23:18Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo Længlich,</p> <p><offtopic></p> <blockquote> <p>Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)</p> </blockquote> <p>Aha, und "Voghdzuyin!" wäre dann wohl klingonisch ;)</p> <blockquote> <p>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. :-)</p> </blockquote> <p>Geht mir ähnlich :)</p> <p></offtopic></p> <blockquote> <p>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.</p> </blockquote> <p>Stimmt auffallend.</p> <blockquote> <p>Beide brauchen, wenn ich das richtig sehe, log₂($n) Durchläufe.</p> </blockquote> <p>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:<br> 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 ;-)</p> <blockquote> <p>Ergebnisse von 5 Script-Aufrufen (in sec):</p> </blockquote> <p>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?</p> <blockquote> <p>Don P: 0.44359087944<br> Længlich: 0.278346061707<br> Don P: 0.409577131271<br> Længlich: 0.289813995361<br> Don P: 0.392857074738<br> Længlich: 0.295516967773<br> Don P: 0.398221969604<br> Længlich: 0.284239053726<br> Don P: 0.409832954407<br> Længlich: 0.280338048935</p> </blockquote> <p>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...</p> <blockquote> <p>Dann habe ich noch versucht, Deine Prüfung (<code class="language-php"><span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token variable">$n</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token variable">$n</span><span class="token punctuation">;</span></code>) 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).</p> </blockquote> <p>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.</p> <blockquote> <p>Hast Du in Javascript die Zeit gemessen? Sah das da anders aus?</p> </blockquote> <p>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...</p> <p>Danke jedenfalls für deine ernüchternden Messungen.</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188751#m1188751 Længlich http://www.grinningbit.com 2007-12-07T19:07:45Z 2007-12-07T19:07:45Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Qapla'!</p> <blockquote> <p><offtopic></p> <blockquote> <p>Meine Postings fangen (fast) immer mit »Hallo!« an; nur die Sprache wechselt. ;-)<br> Aha, und "Voghdzuyin!" wäre dann wohl klingonisch ;)</p> </blockquote> </blockquote> <p>Nein, armenisch. »Qapla'!« ist klingonisch. ;-)</p> <blockquote> <p></offtopic></p> <blockquote> <p>[...]<br> 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:<br> 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.</p> </blockquote> </blockquote> <p>Ah ja, hast recht. Das erkaufst Du Dir allerdings mit der wesentlich aufwendigeren Überprüfung.</p> <blockquote> <p>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 ;-)</p> </blockquote> <p>Die Zweierpotenzen werden allerdings bei höheren Zahlen immer seltener, so daß die Ersparnis immer unwahrscheinlicher wird. Also wieder testen. ;-)</p> <blockquote> <blockquote> <p>Ergebnisse von 5 Script-Aufrufen (in sec):<br> 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?</p> </blockquote> </blockquote> <p>Das Testscript sah so aus:</p> <pre><code class="block language-php"> <span class="token variable">$time</span> <span class="token operator">=</span> <span class="token function">microtime</span><span class="token punctuation">(</span><span class="token constant boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token variable">$n</span> <span class="token operator"><</span> <span class="token number">60000</span><span class="token punctuation">;</span> <span class="token variable">$n</span><span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$v</span> <span class="token operator">=</span> <span class="token function">DonPAlgorithm</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">echo</span><span class="token punctuation">(</span><span class="token string double-quoted-string">"\nDon P: "</span> <span class="token operator">.</span> <span class="token punctuation">(</span><span class="token function">microtime</span><span class="token punctuation">(</span><span class="token constant boolean">true</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token variable">$time</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token variable">$time</span> <span class="token operator">=</span> <span class="token function">microtime</span><span class="token punctuation">(</span><span class="token constant boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token variable">$n</span> <span class="token operator"><</span> <span class="token number">60000</span><span class="token punctuation">;</span> <span class="token variable">$n</span><span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$v</span> <span class="token operator">=</span> <span class="token function">LaenglichAlgorithm</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">echo</span><span class="token punctuation">(</span><span class="token string double-quoted-string">"\nLænglich: "</span> <span class="token operator">.</span> <span class="token punctuation">(</span><span class="token function">microtime</span><span class="token punctuation">(</span><span class="token constant boolean">true</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token variable">$time</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> </code></pre> <p>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.</p> <p>Und jetzt testen wir mal mit 1,2 Mio - 1 Rechnungen:<br> Don P: 8.82406592369<br> Længlich: 6.48715186119<br> Don P: 8.70618391037<br> Længlich: 6.52737307549<br> Don P: 8.61320590973<br> Længlich: 6.48604202271</p> <p>Meins ist immer noch schneller. 2,2 Mio - 1:<br> Don P: 16.45282197<br> Længlich: 12.4065210819</p> <p>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. ;-)</p> <blockquote> <p>Nein, die Mühe und anschließende Schmach erspare ich mir lieber.</p> </blockquote> <p>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. ;-)</p> <blockquote> <p>Bitweise Operationen sind in JavaScript bekannterweise langsam, weil dabei intern noch Integer-Floatingpoint-Umwandlungen stattfinden müssen.</p> </blockquote> <p>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.</p> <p>Viele Grüße vom Længlich</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188761#m1188761 Don P 2007-12-05T23:30:33Z 2007-12-05T23:30:33Z Jetzt aber hoffentlich die Lösung... <p>Hallo,</p> <p>Andere Variante:</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>Die Vergleich lautet also:</p> <p>(n-1)&n == 0</p> <p>Er liefert true für Zweierpotenzen n > 1, sonst false.</p> <p>Das scheint jetzt nun wirklich zu funktionieren. Habe es in vielen Varianten ausprobiert und es ergibt sich schon rein durch die Logik.</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188759#m1188759 ChrisB 2007-12-06T05:46:02Z 2007-12-06T05:46:02Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hi,</p> <blockquote> <p>Wie zählt man nun am besten Bits?</p> </blockquote> <p><code class="language-php"><span class="token function">substr_count</span><span class="token punctuation">(</span><span class="token function">decbin</span><span class="token punctuation">(</span><span class="token variable">$integer</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token string single-quoted-string">'1'</span><span class="token punctuation">)</span></code></p> <p>MfG ChrisB</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188754#m1188754 Blaubart 2007-12-06T19:51:18Z 2007-12-06T19:51:18Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Tach.</p> <blockquote> <p>Wie zählt man nun am besten Bits? Da gibt es einen schönen Trick: <a href="http://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/" rel="nofollow noopener noreferrer">MIT HAKMEM</a></p> </blockquote> <p>Wow, das ist wirklich sehr clever.</p> <blockquote> <p>Da man in PHP nicht direkt Oktalzahlen schreiben kann, funktioniert der dort angegebene C-Code natürlich nicht 1:1.</p> </blockquote> <p>Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...</p> <div class="signature">-- <br> Once is a mistake, twice is Jazz.<br> </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188755#m1188755 Christian Seiler self@christian-seiler.de 2007-12-06T20:41:52Z 2007-12-06T20:41:52Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <blockquote> <p>Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...</p> </blockquote> <p>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...</p> <p>Viele Grüße,<br> Christian</p> <div class="signature">-- <br> <a href="http://del.icio.us/chris_se/servertipps" rel="nofollow noopener noreferrer">Mein "Weblog"</a> [<a href="http://del.icio.us/rss/chris_se/servertipps" rel="nofollow noopener noreferrer">RSS</a>] </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188756#m1188756 Blaubart 2007-12-06T21:15:34Z 2007-12-06T21:15:34Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Tach.</p> <blockquote> <blockquote> <p>Was genau meinst Du? PHP kennt doch die Oktalnotation aus C ...</p> </blockquote> <p>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...</p> </blockquote> <p>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.</p> <p>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?</p> <div class="signature">-- <br> Once is a mistake, twice is Jazz.<br> </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188757#m1188757 Christian Seiler self@christian-seiler.de 2007-12-06T21:34:26Z 2007-12-06T21:34:26Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <blockquote> <p>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?</p> </blockquote> <p>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.</p> <p>Beispiel:</p> <pre><code class="block language-php"><span class="token php language-php"><span class="token delimiter important"><?php</span> <span class="token function">var_dump</span> <span class="token punctuation">(</span><span class="token number">0xDB6DB6DB</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token variable">$x</span> <span class="token operator">=</span> <span class="token number">0xDB6DB6DB</span><span class="token punctuation">;</span> <span class="token function">var_dump</span> <span class="token punctuation">(</span><span class="token variable">$x</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">var_dump</span> <span class="token punctuation">(</span><span class="token number">0xDB6DB6DB</span> <span class="token operator">|</span> <span class="token number">0x00</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">var_dump</span> <span class="token punctuation">(</span><span class="token variable">$x</span> <span class="token operator">|</span> <span class="token number">0x00</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token variable">$y</span> <span class="token operator">=</span> <span class="token number">0xDB6DB6DB</span> <span class="token operator">|</span> <span class="token number">0x00</span><span class="token punctuation">;</span> <span class="token function">var_dump</span> <span class="token punctuation">(</span><span class="token variable">$y</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token delimiter important">?></span></span> </code></pre> <p>Ergibt auf 32bit-Systemen:</p> <p>float(3681400539)<br> float(3681400539)<br> int(-613566757)<br> int(-613566757)<br> int(-613566757)</p> <p>(Das Minuszeichen kommt daher, dass die Zahl größer ist, als die größte mit PHP darstellbare vorzeichenlose Zahl)</p> <p>Viele Grüße,<br> Christian</p> <div class="signature">-- <br> <a href="http://del.icio.us/chris_se/servertipps" rel="nofollow noopener noreferrer">Mein "Weblog"</a> [<a href="http://del.icio.us/rss/chris_se/servertipps" rel="nofollow noopener noreferrer">RSS</a>] </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188758#m1188758 Blaubart 2007-12-06T21:46:45Z 2007-12-06T21:46:45Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Tach.</p> <blockquote> <p>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.</p> </blockquote> <p>Ah, interessant. Darauf, letzteres mal zu überprüfen, hätte ich eigentlich selber kommen können, LOL. Danke für die Info.</p> <div class="signature">-- <br> Once is a mistake, twice is Jazz.<br> </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188760#m1188760 Christian Seiler self@christian-seiler.de 2007-12-06T06:29:44Z 2007-12-06T06:29:44Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo Chris,</p> <blockquote> <blockquote> <p>Wie zählt man nun am besten Bits?</p> </blockquote> <p><code class="language-php"><span class="token function">substr_count</span><span class="token punctuation">(</span><span class="token function">decbin</span><span class="token punctuation">(</span><span class="token variable">$integer</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token string single-quoted-string">'1'</span><span class="token punctuation">)</span></code></p> </blockquote> <p>Och, das wäre doch langweilig. ;-)</p> <p>Viele Grüße,<br> Christian</p> <div class="signature">-- <br> <a href="http://del.icio.us/chris_se/servertipps" rel="nofollow noopener noreferrer">Mein "Weblog"</a> [<a href="http://del.icio.us/rss/chris_se/servertipps" rel="nofollow noopener noreferrer">RSS</a>] </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188762#m1188762 Don P 2007-12-06T06:21:46Z 2007-12-06T06:21:46Z Jetzt aber hoffentlich die Lösung... <p>Hallo,</p> <p>Muss noch erwähnen, dass ich das nur theoretisch (rein mathematisch) ausprobiert habe, nicht wirklich in PHP.</p> <p>Und die Aufgabe war ja eigentlich, falls nötig die nächst höhere Zweierpotenz zu ermitteln.</p> <p>Das geht dann etwa so:</p> <pre><code class="block language-php"> <span class="token keyword">function</span> <span class="token function-definition function">naechsteZweierPotenz</span><span class="token punctuation">(</span> <span class="token variable">$n</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">&</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token variable">$n</span><span class="token punctuation">;</span> <span class="token variable">$p</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">&</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token number">0</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$n</span> <span class="token operator">>></span><span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token variable">$p</span><span class="token operator">++</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token variable">$n</span> <span class="token operator"><<</span> <span class="token variable">$p</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> </code></pre> <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.</p> <p>Möglicherweise shiftet PHP aber anders, und nicht alle Betriebssysteme verwalten die Bits in derselben Reihenfolge :-(.</p> <p>Im Zweifel könnte man die Funktion ohne Shiften so notieren:</p> <pre><code class="block language-php"> <span class="token keyword">function</span> <span class="token function-definition function">naechsteZweierPotenz</span><span class="token punctuation">(</span> <span class="token variable">$n</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">&</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token variable">$n</span><span class="token punctuation">;</span> <span class="token variable">$p</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span><span class="token variable">$n</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&</span> <span class="token variable">$n</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token variable">$n</span> <span class="token operator">&</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token variable">$n</span><span class="token operator">--</span><span class="token punctuation">;</span> <span class="token variable">$n</span> <span class="token operator">/=</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token variable">$p</span><span class="token operator">++</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token variable">$n</span> <span class="token operator">*</span> <span class="token function">pow</span><span class="token punctuation">(</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token variable">$p</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> </code></pre> <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).</p> <p>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...</p> <p>Mit etwas weniger Code, dafür wohl im Schnitt auch ein bisschen langsamer:</p> <pre><code class="block language-php"> <span class="token keyword">function</span> <span class="token function-definition function">naechsteZweierPotenz</span><span class="token punctuation">(</span> <span class="token variable">$n</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token variable">$n</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">&</span><span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token variable">$n</span><span class="token punctuation">;</span> <span class="token variable">$p</span> <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span> <span class="token variable">$p</span> <span class="token operator"><</span> <span class="token variable">$n</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token variable">$p</span> <span class="token operator">*=</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token variable">$p</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> </code></pre> <p>Wie gesagt, alles ungetestet. Sollte aber wesentlich schneller sein als Logarithmieren oder Bits zählen.</p> <p>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 ;-))</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188768#m1188768 Don P 2007-12-05T19:53:17Z 2007-12-05T19:53:17Z Nachtrag <p>Hallo,</p> <p>Diese größtmögliche Zahl kann man ja evtl. durch negieren der 0 erhalten. Der Vergleich</p> <p>~(n^~0) == n</p> <p>müsste es dann eigentlich tun, jedenfalls für positive n, d.h. unsigned Integer, wenn ich nicht irre...</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188764#m1188764 Der Martin self@kennst.net 2007-12-05T19:58:15Z 2007-12-05T19:58:15Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo Don,</p> <blockquote> <p>Zweierpotenzen haben ja die Eigenschaft, in Binärdarstellung genau eine 1 aufzuweisen (das höchste Bit).</p> </blockquote> <p>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.</p> <blockquote> <p>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...</p> </blockquote> <p>You are on the wooden way. ;-)</p> <blockquote> <p>Dann liefert IMHO der Vergleich<br> ~(n^m) == n<br> true, falls n eine Zweierpotenz ist, andernfalls false.</p> </blockquote> <p>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.</p> <p>So long,<br>  Martin</p> <div class="signature">-- <br> Die letzten Worte des stotternden Beifahrers:<br> Frei... frei... frei... freilich kommt da was!! </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188765#m1188765 Don P 2007-12-05T20:23:47Z 2007-12-05T20:23:47Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <blockquote> <blockquote> <p>Dann liefert IMHO der Vergleich<br> ~(n^m) == n<br> true, falls n eine Zweierpotenz ist, andernfalls false.</p> </blockquote> <p>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.</p> </blockquote> <p>Meinst du wirklich? XOR liefert doch nur dann 1, wenn die Bits verschieden sind, sonst 0. Also z.B. so:</p> <p>n = 0100 (Zweierpotenz)<br> ~0000 sei 1111 (also unsere größte Zahl)</p> <p>somit:<br> n XOR m = 1011<br> und dann negiert:<br> 0100<br> was wieder unsere Ausgangszahl ist.</p> <p>Wenn n keine Zweierpotenz ist, kommrn wir aber nicht mehr zur Ausgangszahl zurück, q.e.d.</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188766#m1188766 steckl stefan-stoeckl@gmx.de 2007-12-05T20:33:46Z 2007-12-05T20:33:46Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hi,</p> <p>Mal eine kleine Änderung:</p> <p>n = 0111 (keine Zweierpotenz)<br> ~0000 sei 1111 (also unsere größte Zahl)</p> <p>somit:<br> n XOR m = 1000</p> <p>0111<br> xor 1111<br> --------<br>     1000</p> <p>und dann negiert:<br> 0111</p> <p>In diesem Beispiel auch wieder die Ausgangszahl</p> <blockquote> <p>Wenn n keine Zweierpotenz ist, kommen wir aber nicht mehr zur Ausgangszahl zurück, q.e.d.</p> </blockquote> <p>Eben schon.</p> <p>mfG,<br> steckl</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188767#m1188767 Don P 2007-12-05T21:55:11Z 2007-12-05T21:55:11Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo,</p> <p>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... ;-)</p> <p>Gruß, Don P</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188771#m1188771 flying sheep 2007-12-05T18:34:20Z 2007-12-05T18:34:20Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>verzeihung: anfängerfehler: ich hab das php überlesen.<br> ich kenne mich mit php nicht aus, aber mein system ist hoffendlich übertragbar?</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188770#m1188770 Alexander (HH) 2007-12-05T20:30:11Z 2007-12-05T20:30:11Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Moin Moin!</p> <blockquote> <p>teile durch zwei und runde ab.<br> multipliziere das ergebnis mit 2 und schau nach ob die zahl vorher = der zahl nachher ist.</p> </blockquote> <p>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.</p> <p>Alexander</p> <div class="signature">-- <br> Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". </div> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188772#m1188772 mike 2007-12-05T18:39:47Z 2007-12-05T18:39:47Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <blockquote> <p>verzeihung: anfängerfehler: ich hab das php überlesen.<br> ich kenne mich mit php nicht aus, aber mein system ist hoffendlich übertragbar?</p> </blockquote> <p>fuktioniert wohl irgendwie nicht... ich weiß grad auch nicht warum. Ich bekomme immer "false".</p> <p>Jedenfalls danke für deinen Ansatz...</p> <p>Mike</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188774#m1188774 mike 2007-12-05T18:47:48Z 2007-12-05T18:47:48Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Ich kann mit dem Ansatz gerade nicht viel anfangen:</p> <p>Bsp: Zahl ist 10   (also keine Zweierpotenz => "false")</p> <p>12/2 = 6<br>     6*2 = 12<br>     abrunden: 12    => ist gleich der anfangszahl, also ?true?</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188773#m1188773 Norbert 2007-12-05T18:50:50Z 2007-12-05T18:50:50Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>Hallo Mike,</p> <pre><code class="block language-php"><span class="token php language-php"><span class="token delimiter important"><?php</span> <span class="token variable">$xx</span> <span class="token operator">=</span> <span class="token number">123456789</span><span class="token punctuation">;</span> <span class="token comment">/* Deliquent */</span> <span class="token keyword">echo</span> <span class="token function">ceil</span><span class="token punctuation">(</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token variable">$xx</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token delimiter important">?></span></span> </code></pre> <p>Ceil - liefert die naechste ganze Zahl die groesser oder gleich dem Parameter ist.</p> <p>Gruss Norbert</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188775#m1188775 mike 2007-12-05T18:52:51Z 2007-12-05T18:52:51Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <p>OK, jetzt hab ich's kapiert:</p> <p>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,...</p> <p>Weiß niemand eine Lösung?</p> <p>Mike</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188776#m1188776 Norbert 2007-12-05T18:56:04Z 2007-12-05T18:56:04Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <blockquote> <p>Weiß niemand eine Lösung?</p> </blockquote> <p>ja,<br> steht ein bissel weiter oben ...</p> <p>Gruss Norbert</p> https://forum.selfhtml.org/self/2007/dec/5/wie-pruefe-ich-eine-zahl-auf-zweierpotenz-2-4-8-16/1188777#m1188777 mike 2007-12-05T19:13:52Z 2007-12-05T19:13:52Z Wie prüfe ich eine Zahl auf Zweierpotenz (2,4,8,16,...)? <blockquote> <blockquote> <p>Weiß niemand eine Lösung?<br> ja,<br> steht ein bissel weiter oben ...</p> </blockquote> <p>Gruss Norbert</p> </blockquote> <p>Oh, mann; Brett vorm Kopf ^^</p> <p>Funktioniert Super! Vielen Dank!</p> <p>Schönen Abend, Mike</p>