Sie könnten das am wenigsten signifikante Bit in n eliminieren bis n eine Potenz von 2 ist Sie das bitweise Operator AND mit n verwenden könnte und n-1, die das niedrigstwertige Bit in n beseitigen würde, bis n eine Potenz von 2 Wenn ursprünglich wäre n eine Potenz von 2 wäre dann alles, was Sie n von 1.
public class MathPow{
public int largestPowerOf2(int n){
if((n & n-1) == 0){ //this checks if n is a power of 2
n--; //Since n is a power of 2 we have to subtract 1
}
while((n & n-1) != 0){ //the while will keep on going until n is a power of 2, in which case n will only have 1 bit on which is the maximum power of 2 less than n. You could eliminate the != 0 but just for clarity I left it in
n = n & n-1; //we will then perform the bitwise operation AND with n and n-1 to eliminate the least significant bit of n
}
return n;
}
}
Erklärung wäre zu tun haben, zu reduzieren, ist:
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 haben 8 (nämlich 2 bis 3. Potenz), seine Binärdarstellung 1 0 00 0, die die größte Leistung von 2 n vor wäre fett ist.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.
Mit einer Zahl n, das ist keine Potenz von 2 und ist nicht 0, wissen wir, dass in der Binärdarstellung n verschiedene Bits an hätten, würden diese Bits nur eine Summe verschiedener Potenzen von 2 darstellen wichtig 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 hatten die während würde 168 (die 10101000 binär ist) und subtrahieren 1, die 167 ist (was 10100111 binär ist). Dann würden wir das bitweise AND auf beiden Zahlen machen. Beispiel:
10101000
& 10100111
------------
10100000
Wir haben jetzt die binäre Zahl 10100000. Wenn wir 1 davon subtrahieren und wir nutzen die bitweise AND auf beiden Zahlen, die wir 10 Millionen bekommen, die 128 ist, die 2 auf die Leistung von 7 .
Beispiel:
10100000
& 10011111
-------------
10000000
Wenn n ursprünglich eine Potenz von 2 sein sollten, dann 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, der wäre 15 (in binär 1111) & 14 (in binär 1110).
Beispiel:
1111
& 1110
--------
1110
Jetzt sind wir mit 14 verlassen wir dann das bitweise durch und mit n und n-1, die 14 (binär 1110) ist & 13 (binär 1101).
Beispiel:
1110
& 1101
---------
1100
Jetzt haben wir 12, und wir brauchen nur noch einen letzten am wenigsten signifikanten Bit zu beseitigen. Wiederum führen wir dann das bitweise UND auf n und n-1 aus, was 12 (in binär 1100) und 11 (in binär 1011) ist.
Beispiel
1100
& 1011
--------
1000
Wir mit 8 schließlich übrig sind, welche weniger die größte Potenz von 2 ist als 16.
Was fügen Sie 'System.out.println (res);' in 'while' hinzu, um den Wert von' res' zu sehen? – johnchen902
Ist Null eine erwartete Eingabe? Oder 1? – harold