How to Check If a Number Is a Power of Two in Java

Introduction

In this lab, you will learn how to efficiently determine if a given number is a power of two in Java. We will explore a clever bitwise operation approach, which is often more performant than traditional methods.

The lab will guide you through implementing and testing this bitwise technique, comparing it with a loop-based approach, and handling edge cases such as non-positive numbers to ensure a robust solution.

Skills Graph

Use Bitwise Operation for Power of Two

In this step, we will explore a clever way to determine if a number is a power of two using bitwise operations in Java. This method is often more efficient than traditional loop-based approaches.

First, let's understand what a power of two is. A power of two is any number that can be expressed as 2 raised to an integer exponent (e.g., 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, and so on). In binary representation, powers of two have a unique pattern: they are represented as a 1 followed by zero or more 0s (e.g., 1 is 1, 2 is 10, 4 is 100, 8 is 1000).

Now, consider the binary representation of a power of two and the number immediately preceding it. For example:

• 8 in binary is 1000
• 7 in binary is 0111

If we perform a bitwise AND operation (&) between a power of two and the number immediately preceding it, the result is always zero. This is because the power of two has a single 1 bit, and the number before it has 0s in that position and 1s in all the positions to the right.

For example, 8 (1000) & 7 (0111) = 0000 (which is 0).

This property holds true for all positive powers of two. Any positive number that is not a power of two will have at least two 1 bits in its binary representation. When you perform a bitwise AND with the number before it, at least one of those 1 bits will align with a 1 bit in the preceding number, resulting in a non-zero value.

So, the condition for a positive number n to be a power of two is (n & (n - 1)) == 0.

Let's create a Java program to implement this check.

1. Open the HelloJava.java file in the WebIDE editor.

2. Replace the existing code with the following:

   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 this code:

   • We define a static method isPowerOfTwo that takes an integer n as input.
   • Inside the method, we check if n is greater than 0 and if the bitwise AND of n and n-1 is equal to 0.
   • The main method demonstrates how to use the isPowerOfTwo method with a few example numbers.

3. Save the file (Ctrl+S or Cmd+S).

4. Compile the Java program in the Terminal:

   javac HelloJava.java

   If there are no errors, the compilation is successful.

5. Run the compiled program:

   java HelloJava

   You should see output similar to this:

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

This output confirms that our bitwise check correctly identifies powers of two.

Test with Loop-Based Approach

In the previous step, we learned a concise way to check for powers of two using bitwise operations. While efficient, it might not be immediately intuitive for beginners. In this step, we will implement a more straightforward approach using a loop, which can help solidify your understanding of the concept.

A number n is a power of two if it can be obtained by repeatedly multiplying 1 by 2. For example:

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

We can use a loop to start with 1 and keep multiplying it by 2, checking if we reach the given number n.

Let's add a new method to our HelloJava.java file that uses a loop to check for powers of two.

1. Open the HelloJava.java file in the WebIDE editor.

2. Add the following method inside the HelloJava class, below the isPowerOfTwo method:

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

   In this new method:

   • We first handle the case where n is not positive, returning false.
   • We initialize a variable power to 1.
   • We use a while loop that continues as long as power is less than n.
   • Inside the loop, we double the value of power in each iteration (power *= 2 is a shorthand for power = power * 2).
   • After the loop finishes, we check if the final value of power is equal to n. If it is, n is a power of two.

3. Now, let's modify the main method to test this new loop-based method. Replace the existing main method with this updated version:

       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
       }

   We've added a test case for 0 and included print statements to clearly show the results from both the bitwise and loop-based methods.

4. Save the file (Ctrl+S or Cmd+S).

5. Compile the updated Java program in the Terminal:

   javac HelloJava.java

6. Run the compiled program:

   java HelloJava

   You should see output similar to this:

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

Both methods produce the same results for these test cases. The loop-based approach is perhaps easier to understand initially, while the bitwise approach is generally more performant, especially for larger numbers.

Handle Non-Positive Numbers

In the previous steps, we implemented two methods to check if a number is a power of two. We briefly touched upon handling non-positive numbers (zero and negative numbers) in the loop-based approach. In this step, we will explicitly focus on why it's important to handle these cases and ensure both our methods correctly return false for non-positive inputs.

By definition, a power of two is a positive integer. Therefore, zero and any negative number cannot be powers of two. Our methods should reflect this.

Let's re-examine our existing methods in HelloJava.java to ensure they correctly handle non-positive numbers.

1. Open the HelloJava.java file in the WebIDE editor.

2. Look at the isPowerOfTwo method (the bitwise one):

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

   This method already includes the check (n > 0). This ensures that if n is zero or negative, the condition (n > 0) will be false, and the entire expression will evaluate to false due to the && operator. So, the bitwise method correctly handles non-positive numbers.

3. Now, look at the isPowerOfTwoLoop method:

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

   This method explicitly checks if (n <= 0) at the beginning and returns false if the condition is true. This also correctly handles non-positive numbers.

4. Let's add more test cases in the main method to specifically check zero and negative numbers. Modify the main method to include negative numbers:

       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. Save the file (Ctrl+S or Cmd+S).

6. Compile the updated Java program:

   javac HelloJava.java

7. Run the compiled program:

   java HelloJava

   You should see output similar to this:

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

As you can see, both methods correctly identify that 0 and negative numbers are not powers of two. This confirms that our implementations are robust for all integer inputs.

Understanding edge cases like non-positive numbers is crucial in programming to ensure your code behaves correctly under all valid inputs.

Summary

In this lab, we learned how to efficiently check if a number is a power of two in Java using bitwise operations. We discovered that a positive number n is a power of two if and only if the result of the bitwise AND operation between n and n-1 is zero. This is due to the unique binary representation of powers of two. We implemented a Java function isPowerOfTwo utilizing this bitwise approach, which is generally more performant than loop-based methods.

We also explored testing this bitwise method and considered how to handle non-positive numbers, ensuring our check is robust for various inputs. This hands-on experience provided practical insight into applying bitwise operations for solving common programming problems.