Как проверить, является ли число степенью двойки на Java

Введение

В этом лабораторном занятии (LabEx) вы научитесь эффективно определять, является ли заданное число степенью двойки на Java. Мы рассмотрим хитрый подход, основанный на битовых операциях, который часто более эффективен, чем традиционные методы.

В рамках лабораторного занятия (LabEx) вы будете пошагово реализовывать и тестировать этот битовый метод, сравнивать его с подходом на основе цикла и обрабатывать крайние случаи, такие как неположительные числа, чтобы обеспечить надежное решение.

Skills Graph

Использование битовых операций для определения степени двойки

На этом этапе мы рассмотрим хитрый способ определить, является ли число степенью двойки с использованием битовых операций на Java. Этот метод часто более эффективен, чем традиционные подходы, основанные на циклах.

Сначала разберемся, что такое степень двойки. Степенью двойки называется любое число, которое может быть представлено в виде 2 в целой степени (например, 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8 и так далее). В двоичном представлении степени двойки имеют уникальную закономерность: они представляются в виде 1, за которым следуют ноль или более 0 (например, 1 - это 1, 2 - это 10, 4 - это 100, 8 - это 1000).

Теперь рассмотрим двоичное представление степени двойки и числа, предшествующего ей. Например:

• 8 в двоичной системе - это 1000
• 7 в двоичной системе - это 0111

Если выполнить битовую операцию И (&) между степенью двойки и числом, предшествующим ей, результат всегда будет равен нулю. Это происходит потому, что степень двойки имеет единственный бит 1, а число перед ней имеет 0 в этой позиции и 1 во всех позициях справа.

Например, 8 (1000) & 7 (0111) = 0000 (что равно 0).

Это свойство справедливо для всех положительных степеней двойки. Любое положительное число, которое не является степенью двойки, будет иметь в своем двоичном представлении как минимум два бита 1. При выполнении битовой операции И с предыдущим числом как минимум один из этих битов 1 совпадет с битом 1 в предыдущем числе, в результате чего получится ненулевое значение.

Таким образом, условие того, что положительное число n является степенью двойки, можно записать как (n & (n - 1)) == 0.

Создадим Java-программу для реализации этой проверки.

1. Откройте файл HelloJava.java в редакторе WebIDE.

2. Замените существующий код следующим:

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

   В этом коде:

   • Мы определяем статический метод isPowerOfTwo, который принимает целое число n в качестве входного параметра.
   • Внутри метода мы проверяем, что n больше 0 и что битовая операция И между n и n - 1 равна 0.
   • Метод main демонстрирует, как использовать метод isPowerOfTwo с несколькими примерами чисел.

3. Сохраните файл (Ctrl+S или Cmd+S).

4. Скомпилируйте Java-программу в терминале:

   javac HelloJava.java

   Если нет ошибок, компиляция прошла успешно.

5. Запустите скомпилированную программу:

   java HelloJava

   Вы должны увидеть вывод, похожий на следующий:

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

Этот вывод подтверждает, что наша битовая проверка правильно определяет степени двойки.

Тестирование подхода на основе цикла

На предыдущем этапе мы узнали лаконичный способ проверки, является ли число степенью двойки, с использованием битовых операций. Несмотря на свою эффективность, этот метод может не сразу показаться интуитивно понятным для начинающих. На этом этапе мы реализуем более простой подход с использованием цикла, который поможет укрепить ваше понимание концепции.

Число n является степенью двойки, если его можно получить путем многократного умножения 1 на 2. Например:

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

Мы можем использовать цикл, начиная с 1 и последовательно умножая его на 2, и проверять, достигнем ли мы заданного числа n.

Добавим новый метод в файл HelloJava.java, который будет использовать цикл для проверки, является ли число степенью двойки.

1. Откройте файл HelloJava.java в редакторе WebIDE.

2. Добавьте следующий метод внутри класса HelloJava, ниже метода 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
       }

   В этом новом методе:

   • Сначала обрабатываем случай, когда n не является положительным числом, и возвращаем false.
   • Инициализируем переменную power значением 1.
   • Используем цикл while, который продолжается, пока power меньше n.
   • Внутри цикла удваиваем значение power на каждой итерации (power *= 2 - это сокращенная запись для power = power * 2).
   • После завершения цикла проверяем, равно ли конечное значение power числу n. Если равно, то n является степенью двойки.

3. Теперь изменим метод main для тестирования этого нового метода, основанного на цикле. Замените существующий метод main на следующую обновленную версию:

       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
       }

   Мы добавили тестовый случай для 0 и включили строки вывода, чтобы четко показать результаты как битового, так и циклического методов.

4. Сохраните файл (Ctrl+S или Cmd+S).

5. Скомпилируйте обновленную Java-программу в терминале:

   javac HelloJava.java

6. Запустите скомпилированную программу:

   java HelloJava

   Вы должны увидеть вывод, похожий на следующий:

   --- 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

Оба метода дают одинаковые результаты для этих тестовых случаев. Подход на основе цикла, возможно, легче понять вначале, в то время как битовый подход обычно более эффективен, особенно для больших чисел.

Обработка неположительных чисел

На предыдущих этапах мы реализовали два метода для проверки, является ли число степенью двойки. Мы кратко упомянули о обработке неположительных чисел (нуля и отрицательных чисел) в подходе на основе цикла. На этом этапе мы сосредоточимся на том, почему важно обрабатывать эти случаи и убедимся, что оба наши метода правильно возвращают false для неположительных входных данных.

По определению, степень двойки - это положительное целое число. Поэтому ноль и любое отрицательное число не могут быть степенями двойки. Наши методы должны отражать это.

Пересмотрим наши существующие методы в файле HelloJava.java, чтобы убедиться, что они правильно обрабатывают неположительные числа.

1. Откройте файл HelloJava.java в редакторе WebIDE.

2. Посмотрите на метод isPowerOfTwo (битовый метод):

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

   Этот метод уже содержит проверку (n > 0). Это гарантирует, что если n равно нулю или отрицательному числу, условие (n > 0) будет false, и вся выражение будет равно false из-за оператора &&. Таким образом, битовый метод правильно обрабатывает неположительные числа.

3. Теперь посмотрите на метод 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;
       }

   Этот метод явно проверяет if (n <= 0) в начале и возвращает false, если условие истинно. Это также правильно обрабатывает неположительные числа.

4. Добавим больше тестовых случаев в метод main, чтобы специально проверить ноль и отрицательные числа. Измените метод main, чтобы включить отрицательные числа:

       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. Сохраните файл (Ctrl+S или Cmd+S).

6. Скомпилируйте обновленную Java-программу:

   javac HelloJava.java

7. Запустите скомпилированную программу:

   java HelloJava

   Вы должны увидеть вывод, похожий на следующий:

   --- 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

Как вы можете видеть, оба метода правильно определяют, что 0 и отрицательные числа не являются степенями двойки. Это подтверждает, что наши реализации надежны для всех целочисленных входных данных.

Понимание граничных случаев, таких как неположительные числа, является важной частью программирования, чтобы обеспечить правильное поведение кода при всех допустимых входных данных.

Резюме

В этом практическом занятии (лабораторной работе) мы научились эффективно проверять, является ли число степенью двойки на Java с использованием битовых операций. Мы обнаружили, что положительное число n является степенью двойки тогда и только тогда, когда результат битовой операции И между n и n - 1 равен нулю. Это обусловлено уникальным двоичным представлением степеней двойки. Мы реализовали функцию Java isPowerOfTwo, используя этот битовый подход, который обычно более эффективен, чем методы на основе циклов.

Мы также исследовали тестирование этого битового метода и рассмотрели, как обрабатывать неположительные числа, чтобы обеспечить надежность нашей проверки для различных входных данных. Этот практический опыт дал полезные знания о применении битовых операций для решения распространенных задач программирования.