Comment vérifier si un nombre est une puissance de deux en Java

Introduction

Dans ce laboratoire (lab), vous apprendrez à déterminer efficacement si un nombre donné est une puissance de deux en Java. Nous allons explorer une approche astucieuse utilisant les opérations au niveau des bits (bitwise operations), qui est souvent plus performante que les méthodes traditionnelles.

Le laboratoire vous guidera tout au long de la mise en œuvre et des tests de cette technique au niveau des bits, en la comparant avec une approche basée sur une boucle (loop-based approach), et en gérant les cas limites tels que les nombres non positifs pour garantir une solution robuste.

Skills Graph

Utilisation des opérations au niveau des bits (bitwise operations) pour vérifier si un nombre est une puissance de deux

Dans cette étape, nous allons explorer une méthode astucieuse pour déterminer si un nombre est une puissance de deux en utilisant les opérations au niveau des bits (bitwise operations) en Java. Cette méthode est souvent plus efficace que les approches traditionnelles basées sur des boucles (loop-based approaches).

Tout d'abord, comprenons ce qu'est une puissance de deux. Une puissance de deux est tout nombre qui peut s'exprimer comme 2 élevé à un exposant entier (par exemple, 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, etc.). En représentation binaire, les puissances de deux ont un motif unique : elles sont représentées par un 1 suivi de zéro ou plusieurs 0 (par exemple, 1 est 1, 2 est 10, 4 est 100, 8 est 1000).

Maintenant, considérons la représentation binaire d'une puissance de deux et du nombre qui la précède immédiatement. Par exemple :

• 8 en binaire est 1000
• 7 en binaire est 0111

Si nous effectuons une opération ET au niveau des bits (&) entre une puissance de deux et le nombre qui la précède immédiatement, le résultat est toujours zéro. En effet, la puissance de deux a un seul bit 1, et le nombre qui la précède a des 0 à cette position et des 1 dans toutes les positions à droite.

Par exemple, 8 (1000) & 7 (0111) = 0000 (ce qui équivaut à 0).

Cette propriété est valable pour toutes les puissances de deux positives. Tout nombre positif qui n'est PAS une puissance de deux aura au moins deux bits 1 dans sa représentation binaire. Lorsque vous effectuez un ET au niveau des bits avec le nombre qui le précède, au moins l'un de ces bits 1 coïncidera avec un bit 1 du nombre précédent, donnant un résultat non nul.

Ainsi, la condition pour qu'un nombre positif n soit une puissance de deux est (n & (n - 1)) == 0.

Créons un programme Java pour implémenter cette vérification.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE.

2. Remplacez le code existant par le suivant :

   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));
       }
   }

   Dans ce code :

   • Nous définissons une méthode statique isPowerOfTwo qui prend un entier n en entrée.
   • À l'intérieur de la méthode, nous vérifions si n est supérieur à 0 et si l'opération ET au niveau des bits de n et n - 1 est égale à 0.
   • La méthode main montre comment utiliser la méthode isPowerOfTwo avec quelques nombres d'exemple.

3. Enregistrez le fichier (Ctrl+S ou Cmd+S).

4. Compilez le programme Java dans le terminal :

   javac HelloJava.java

   S'il n'y a pas d'erreurs, la compilation est réussie.

5. Exécutez le programme compilé :

   java HelloJava

   Vous devriez voir une sortie similaire à ceci :

   8 is a power of two: true
   12 is a power of two: false
   1 is a power of two: true

Cette sortie confirme que notre vérification au niveau des bits identifie correctement les puissances de deux.

Test avec une approche basée sur une boucle (loop-based approach)

Dans l'étape précédente, nous avons appris une méthode concise pour vérifier si un nombre est une puissance de deux en utilisant les opérations au niveau des bits (bitwise operations). Bien que cette méthode soit efficace, elle peut ne pas être immédiatement intuitive pour les débutants. Dans cette étape, nous allons implémenter une approche plus simple en utilisant une boucle, ce qui peut vous aider à mieux comprendre le concept.

Un nombre n est une puissance de deux s'il peut être obtenu en multipliant répétitivement 1 par 2. Par exemple :

• 1 = 1 * 2^0
• 2 = 1 * 2^1
• 4 = 1 * 2^2
• 8 = 1 * 2^3

Nous pouvons utiliser une boucle pour commencer par 1 et le multiplier constamment par 2, en vérifiant si nous atteignons le nombre donné n.

Ajoutons une nouvelle méthode à notre fichier HelloJava.java qui utilise une boucle pour vérifier si un nombre est une puissance de deux.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE.

2. Ajoutez la méthode suivante à l'intérieur de la classe HelloJava, en dessous de la méthode isPowerOfTwo :

       // Function to check if a number is a power of two using a loop
       public static boolean isPowerOfTwoLoop(int n) {
           if (n <= 0) {
               return false; // Powers of two are positive
           }
           int power = 1;
           while (power < n) {
               power *= 2; // Multiply by 2 in each iteration
           }
           return power == n; // Check if we reached the original number
       }

   Dans cette nouvelle méthode :

   • Nous traitons d'abord le cas où n n'est pas positif, en renvoyant false.
   • Nous initialisons une variable power à 1.
   • Nous utilisons une boucle while qui continue tant que power est inférieur à n.
   • À l'intérieur de la boucle, nous doublons la valeur de power à chaque itération (power *= 2 est une forme abrégée de power = power * 2).
   • Après que la boucle se termine, nous vérifions si la valeur finale de power est égale à n. Si c'est le cas, n est une puissance de deux.

3. Maintenant, modifions la méthode main pour tester cette nouvelle méthode basée sur une boucle. Remplacez la méthode main existante par cette version mise à jour :

       public static void main(String[] args) {
           int number1 = 8;
           int number2 = 12;
           int number3 = 1;
           int number4 = 0; // Test a non-positive number
   
           System.out.println("--- Using Bitwise Approach ---");
           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));
           System.out.println(number4 + " is a power of two: " + isPowerOfTwo(number4)); // Test with 0
   
           System.out.println("\n--- Using Loop Approach ---");
           System.out.println(number1 + " is a power of two: " + isPowerOfTwoLoop(number1));
           System.out.println(number2 + " is a power of two: " + isPowerOfTwoLoop(number2));
           System.out.println(number3 + " is a power of two: " + isPowerOfTwoLoop(number3));
           System.out.println(number4 + " is a power of two: " + isPowerOfTwoLoop(number4)); // Test with 0
       }

   Nous avons ajouté un cas de test pour 0 et inclus des instructions d'impression pour montrer clairement les résultats des méthodes basées sur les opérations au niveau des bits et sur la boucle.

4. Enregistrez le fichier (Ctrl+S ou Cmd+S).

5. Compilez le programme Java mis à jour dans le terminal :

   javac HelloJava.java

6. Exécutez le programme compilé :

   java HelloJava

   Vous devriez voir une sortie similaire à ceci :

   --- Using Bitwise Approach ---
   8 is a power of two: true
   12 is a power of two: false
   1 is a power of two: true
   0 is a power of two: false
   
   --- Using Loop Approach ---
   8 is a power of two: true
   12 is a power of two: false
   1 is a power of two: true
   0 is a power of two: false

Les deux méthodes produisent les mêmes résultats pour ces cas de test. L'approche basée sur une boucle est peut-être plus facile à comprendre au départ, tandis que l'approche basée sur les opérations au niveau des bits est généralement plus performante, surtout pour les nombres plus grands.

Gérer les nombres non positifs

Dans les étapes précédentes, nous avons implémenté deux méthodes pour vérifier si un nombre est une puissance de deux. Nous avons brièvement abordé le traitement des nombres non positifs (zéro et nombres négatifs) dans l'approche basée sur une boucle. Dans cette étape, nous allons nous concentrer explicitement sur la raison pour laquelle il est important de gérer ces cas et nous assurer que nos deux méthodes retournent correctement false pour les entrées non positives.

Par définition, une puissance de deux est un entier positif. Par conséquent, zéro et tout nombre négatif ne peuvent pas être des puissances de deux. Nos méthodes devraient refléter cela.

Réexaminons nos méthodes existantes dans le fichier HelloJava.java pour nous assurer qu'elles gèrent correctement les nombres non positifs.

1. Ouvrez le fichier HelloJava.java dans l'éditeur WebIDE.

2. Regardez la méthode isPowerOfTwo (celle basée sur les opérations au niveau des bits) :

       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);
       }

   Cette méthode inclut déjà la vérification (n > 0). Cela garantit que si n est zéro ou négatif, la condition (n > 0) sera false, et l'expression entière sera évaluée à false en raison de l'opérateur &&. Ainsi, la méthode basée sur les opérations au niveau des bits gère correctement les nombres non positifs.

3. Maintenant, regardez la méthode isPowerOfTwoLoop :

       public static boolean isPowerOfTwoLoop(int n) {
           if (n <= 0) {
               return false; // Powers of two are positive
           }
           int power = 1;
           while (power < n) {
               power *= 2;
           }
           return power == n;
       }

   Cette méthode vérifie explicitement if (n <= 0) au début et retourne false si la condition est vraie. Cela gère également correctement les nombres non positifs.

4. Ajoutons plus de cas de test dans la méthode main pour vérifier spécifiquement zéro et les nombres négatifs. Modifiez la méthode main pour inclure des nombres négatifs :

       public static void main(String[] args) {
           int number1 = 8;
           int number2 = 12;
           int number3 = 1;
           int number4 = 0;
           int number5 = -4; // Test a negative number
           int number6 = -1; // Test another negative number
   
           System.out.println("--- Using Bitwise Approach ---");
           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));
           System.out.println(number4 + " is a power of two: " + isPowerOfTwo(number4));
           System.out.println(number5 + " is a power of two: " + isPowerOfTwo(number5));
           System.out.println(number6 + " is a power of two: " + isPowerOfTwo(number6));
   
           System.out.println("\n--- Using Loop Approach ---");
           System.out.println(number1 + " is a power of two: " + isPowerOfTwoLoop(number1));
           System.out.println(number2 + " is a power of two: " + isPowerOfTwoLoop(number2));
           System.out.println(number3 + " is a power of two: " + isPowerOfTwoLoop(number3));
           System.out.println(number4 + " is a power of two: " + isPowerOfTwoLoop(number4));
           System.out.println(number5 + " is a power of two: " + isPowerOfTwoLoop(number5));
           System.out.println(number6 + " is a power of two: " + isPowerOfTwoLoop(number6));
       }

5. Enregistrez le fichier (Ctrl+S ou Cmd+S).

6. Compilez le programme Java mis à jour :

   javac HelloJava.java

7. Exécutez le programme compilé :

   java HelloJava

   Vous devriez voir une sortie similaire à ceci :

   --- Using Bitwise Approach ---
   8 is a power of two: true
   12 is a power of two: false
   1 is a power of two: true
   0 is a power of two: false
   -4 is a power of two: false
   -1 is a power of two: false
   
   --- Using Loop Approach ---
   8 is a power of two: true
   12 is a power of two: false
   1 is a power of two: true
   0 is a power of two: false
   -4 is a power of two: false
   -1 is a power of two: false

Comme vous pouvez le voir, les deux méthodes identifient correctement que 0 et les nombres négatifs ne sont pas des puissances de deux. Cela confirme que nos implémentations sont robustes pour toutes les entrées entières.

Comprendre les cas limites comme les nombres non positifs est crucial en programmation pour garantir que votre code se comporte correctement pour toutes les entrées valides.

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier efficacement si un nombre est une puissance de deux en Java en utilisant des opérations au niveau des bits (bitwise operations). Nous avons découvert qu'un nombre positif n est une puissance de deux si et seulement si le résultat de l'opération ET au niveau des bits (bitwise AND) entre n et n - 1 est zéro. Cela est dû à la représentation binaire unique des puissances de deux. Nous avons implémenté une fonction Java isPowerOfTwo utilisant cette approche basée sur les opérations au niveau des bits, qui est généralement plus performante que les méthodes basées sur des boucles (loop-based methods).

Nous avons également exploré le test de cette méthode basée sur les opérations au niveau des bits et avons considéré comment gérer les nombres non positifs, en nous assurant que notre vérification est robuste pour diverses entrées. Cette expérience pratique a fourni des informations pratiques sur l'application des opérations au niveau des bits pour résoudre des problèmes de programmation courants.