Change res =(int)Math.pow(res, 2); to res *= 2; Dies wird die nächste Potenz von 2 größer als res zurückgeben.
Das Endergebnis, nach dem Sie suchen, wird also nach dem Ende der Zeit schließlich res / 2 sein.
Um zu verhindern, dass der Code über den Wertbereich von int hinausläuft, sollten Sie den Typ von res in double / long ändern, alles, was höhere Werte als int enthalten kann. Am Ende müsstest du einmal sprechen.
Für n <= 1 macht die Frage keinen Sinn. Was in diesem Bereich zu tun ist, bleibt dem interessierten Leser überlassen.
Das ist eine gute Sammlung von Bit-Twiddling-Algorithmen in Hacker's Delight .
Es gibt eine nette Funktion in Integer , die hilfreich ist, numberOfLeadingZeros .
Damit können Sie
machen %Vor% Was komische Sachen macht, wenn n 0 oder 1 ist, aber für diese Eingaben gibt es keine wohldefinierte "höchste Potenz von zwei weniger als n ".
edit: diese Antwort ist noch besser
Sie könnten das niedrigstwertige Bit in n eliminieren, bis n eine Potenz von 2 ist. Sie könnten den bitweisen Operator AND mit n und n-1 verwenden, der das niedrigstwertige Bit in n eliminiert, bis n eine Potenz von ist 2. Wenn ursprünglich n eine Potenz von 2 wäre, müsste man n nur um 1 reduzieren.
%Vor%ERKLÄRUNG:
Wenn Sie eine Zahl n haben (das ist keine Potenz von 2), ist die größte Potenz von 2, die kleiner als n ist, immer das höchstwertige Bit in n. Im Fall einer Zahl n, die eine Potenz von 2 ist, ist die größte Potenz von 2 kleiner als n das Bit rechts vor dem einzigen Bit, das in n ist.
Zum Beispiel, wenn wir 8 hatten (was 2 zur dritten Potenz ist), ist seine binäre Repräsentation 1 0 00 die 0, die fett ist, wäre die größte Potenz von 2 vor n. Da wir wissen, dass jede binäre Zahl eine Potenz von 2 darstellt, wäre die größte Potenz von 2 kleiner als n die Potenz von 2, wenn wir n als eine Potenz von 2 haben, was das Bit wäre vor dem nur ein bisschen weiter in n.
Bei einer Zahl n, die keine Potenz von 2 ist und nicht 0 ist, wissen wir, dass in der binären Darstellung n verschiedene Bits an wären, diese Bits würden nur eine Summe verschiedener Potenzen von 2 darstellen, die wichtigste von denen wäre das wichtigste Bit. Dann könnten wir folgern, dass n nur das höchstwertige Bit plus einige andere Bits ist. Da n in einer bestimmten Länge von Bits dargestellt ist und das höchstwertige Bit die höchste Potenz von 2 ist, die wir mit dieser Anzahl von Bits darstellen können, aber es ist auch die niedrigste Zahl, die wir mit diesen vielen Bits darstellen können, können wir daraus schließen das höchstwertige Bit ist die höchste Potenz von 2 niedriger als n, denn wenn wir ein weiteres Bit hinzufügen, um die nächste Potenz von 2 darzustellen, haben wir eine Potenz von 2 größer als n.
BEISPIELE:
Zum Beispiel, wenn wir 168 hätten (was 10101000 in binär ist), würde die while 168 nehmen und 1 subtrahieren, was 167 ist (was 10100111 in binär ist). Dann würden wir das bitweise AND auf beiden Zahlen machen. Beispiel:
%Vor%Wir haben jetzt die Binärzahl 10100000. Wenn wir 1 von ihr subtrahieren und wir das bitweise UND für beide Zahlen verwenden, erhalten wir 10000000, was 128 ist, was 2 zur Potenz von 7 ist.
Beispiel:
%Vor%Wenn n ursprünglich eine Potenz von 2 sein sollte, müssen wir 1 von n subtrahieren. Wenn zum Beispiel n 16 ist, was 10000 binär ist, würden wir 1 subtrahieren, was uns 15 zurückgeben würde, was 1111 binär ist, und wir speichern es in n (was das ist, was das tut). Wir gehen dann in die while was den bitweisen Operator AND mit n und n-1 macht, was 15 (in binär 1111) & amp; 14 (in Binär 1110).
Beispiel:
%Vor%Nun sind wir bei 14. Wir führen dann das bitweise UND mit n und n-1 durch, was 14 (binär 1110) & amp; 13 (binär 1101).
Beispiel:
%Vor%Jetzt haben wir 12 und wir müssen nur noch ein letztes niedrigstwertiges Bit eliminieren. Wir führen dann das bitweise UND auf n und n-1 aus, was 12 (in binär 1100) und 11 (in binär 1011) ist.
Beispiel
%Vor%Uns bleibt schließlich 8, was die größte Potenz von 2 unter 16 ist.
Sie quadrieren res jedes Mal, dh Sie berechnen 2^2^2^2 anstelle von 2^k .
Ändern Sie Ihre Bewertung wie folgt:
Aktualisierung:
Natürlich müssen Sie auf Überlauf von int prüfen, in diesem Fall überprüfen
während (res & lt; = (n - 1) / 2)
scheint viel besser.
Hier ist eine rekursive Bit-Shifting-Methode, die ich für diesen Zweck geschrieben habe:
%Vor%Oder kürzere Definition:
%Vor% Also in Ihrer Hauptmethode lassen Sie das Argument z immer gleich 1 . Es ist schade, dass Standardparameter hier nicht verfügbar sind:
Wenn die Zahl eine ganze Zahl ist, können Sie sie immer in eine binäre Zahl ändern und dann die Anzahl der Ziffern herausfinden.
%Vor%Wenn die Zahl eine Zweierpotenz ist, dann ist die Antwort offensichtlich. (nur Bit-Shift) wenn nicht gut dann kann es auch durch Bit-Shifting erreicht werden.
finde die Länge der gegebenen Zahl in binärer Darstellung. (13 in binär = 1101; Länge ist 4)
dann shift 2 by (4-2) // 4 ist die Länge der gegebenen Zahl in binär
Der folgende Java-Code löst das für BigIntegers (also grundsätzlich für alle Zahlen).
%Vor%Ich habe oben eine andere BigInteger-Lösung gesehen, aber das ist eigentlich ziemlich langsam. Ein effektiverer Weg, wenn wir über Integer und Long hinausgehen, ist
%Vor% wobei TWO einfach BigInteger.valueOf(2L)
und BigIntegerMath stammen aus Guava.
Ein bisschen spät, aber ...
(32-Bit-Nummer vorausgesetzt.)
%Vor%Erläuterung:
Der erste | stellt sicher, dass das ursprüngliche obere Bit und das zweithöchste obere Bit gesetzt sind. Der zweite | stellt sicher, dass diese beiden und die nächsten beiden usw. sind, bis Sie möglicherweise alle 32 Bits treffen. Dh
100010101 - & gt; 111111111
Dann entfernen wir alle außer das oberste Bit, indem wir die 1er-Kette mit der 1er-Kette um eins nach links verschieben, und wir enden mit nur dem einen oberen Bit, gefolgt von 0.