Verwendung von bitweisen Operationen für Zweierpotenzen
In diesem Schritt werden wir einen cleveren Weg untersuchen, um zu bestimmen, ob eine Zahl in Java eine Zweierpotenz ist, indem wir bitweise Operationen verwenden. Diese Methode ist oft effizienter als herkömmliche, auf Schleifen basierende Ansätze.
Zunächst verstehen wir, was eine Zweierpotenz ist. Eine Zweierpotenz ist jede Zahl, die als 2 hoch einen ganzzahligen Exponenten ausgedrückt werden kann (z. B. 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, und so weiter). In binärer Darstellung haben Zweierpotenzen ein einzigartiges Muster: Sie werden als eine 1 gefolgt von null oder mehreren 0en dargestellt (z. B. 1 ist 1, 2 ist 10, 4 ist 100, 8 ist 1000).
Betrachten wir nun die binäre Darstellung einer Zweierpotenz und der unmittelbar vorhergehenden Zahl. Beispielsweise:
- 8 in binär ist
1000
- 7 in binär ist
0111
Wenn wir eine bitweise AND-Operation (&) zwischen einer Zweierpotenz und der unmittelbar vorhergehenden Zahl ausführen, ist das Ergebnis immer null. Dies liegt daran, dass die Zweierpotenz ein einzelnes 1-Bit hat, und die vorhergehende Zahl an dieser Position 0en und 1en in allen Positionen rechts davon hat.
Beispielsweise ist 8 (1000) & 7 (0111) = 0000 (was 0 ist).
Diese Eigenschaft gilt für alle positiven Zweierpotenzen. Jede positive Zahl, die keine Zweierpotenz ist, hat in ihrer binären Darstellung mindestens zwei 1-Bits. Wenn Sie eine bitweise AND-Operation mit der vorhergehenden Zahl ausführen, wird mindestens eines dieser 1-Bits mit einem 1-Bit in der vorhergehenden Zahl übereinstimmen, was zu einem nicht-null-Wert führt.
Somit ist die Bedingung für eine positive Zahl n, eine Zweierpotenz zu sein, (n & (n - 1)) == 0.
Erstellen wir ein Java-Programm, um diese Prüfung zu implementieren.
-
Öffnen Sie die Datei HelloJava.java im WebIDE-Editor.
-
Ersetzen Sie den vorhandenen Code durch folgenden:
public class HelloJava {
// Function to check if a number is a power of two using bitwise AND
public static boolean isPowerOfTwo(int n) {
// A number is a power of two if it's positive and (n & (n - 1)) is 0
return (n > 0) && ((n & (n - 1)) == 0);
}
public static void main(String[] args) {
int number1 = 8;
int number2 = 12;
int number3 = 1;
System.out.println(number1 + " is a power of two: " + isPowerOfTwo(number1));
System.out.println(number2 + " is a power of two: " + isPowerOfTwo(number2));
System.out.println(number3 + " is a power of two: " + isPowerOfTwo(number3));
}
}
In diesem Code:
- Wir definieren eine statische Methode
isPowerOfTwo, die eine Ganzzahl n als Eingabe nimmt.
- Innerhalb der Methode überprüfen wir, ob
n größer als 0 ist und ob die bitweise AND-Operation von n und n-1 gleich 0 ist.
- Die
main-Methode zeigt, wie die isPowerOfTwo-Methode mit einigen Beispielzahlen verwendet wird.
-
Speichern Sie die Datei (Strg+S oder Cmd+S).
-
Kompilieren Sie das Java-Programm im Terminal:
javac HelloJava.java
Wenn keine Fehler auftreten, war die Kompilierung erfolgreich.
-
Führen Sie das kompilierte Programm aus:
java HelloJava
Sie sollten eine Ausgabe ähnlich dieser sehen:
8 is a power of two: true
12 is a power of two: false
1 is a power of two: true
Diese Ausgabe bestätigt, dass unsere bitweise Prüfung Zweierpotenzen korrekt erkennt.
