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.

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.

Open the HelloJava.java file in the WebIDE editor.

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.

Save the file (Ctrl+S or Cmd+S).
Compile the Java program in the Terminal:
```
javac HelloJava.java
```
If there are no errors, the compilation is successful.

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.

Open the HelloJava.java file in the WebIDE editor.
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.

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.

Save the file (Ctrl+S or Cmd+S).
Compile the updated Java program in the Terminal:
```
javac HelloJava.java
```

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.

Open the HelloJava.java file in the WebIDE editor.
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.

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.

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

Save the file (Ctrl+S or Cmd+S).
Compile the updated Java program:
```
javac HelloJava.java
```

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.