Java: Check whether an given integer is power of 2 or not using O(1) time

Last update on April 01 2025 10:52:09 (UTC/GMT +8 hours)

Check If Power of Two in O(1)

Write a Java program to check whether an integer is a power of 2 or not using O(1) time.

Note: O(1) means that it takes a constant time, like 12 nanoseconds, or two minutes no matter the amount of data in the set.
O(n) means it takes an amount of time linear with the size of the set, so a set twice the size will take twice the time. You probably don't want to put a million objects into one of these.

Visualization of powers of two from 1 to 1024:

Sample Solution:

Java Code:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Initialize a boolean variable
        boolean b = true;

        // Create a Scanner object for user input
        Scanner in = new Scanner(System.in);

        // Prompt the user to input a number
        System.out.print("Input a number: ");
        int num = in.nextInt();

        // Start a block of code
        {
            // Continue looping until num becomes 1
            while (num != 1) {
                // Check if num is odd
                if (num % 2 != 0) {
                    // Toggle the boolean variable
                    b = !b;

                    // Print the current value of the boolean variable and exit the program
                    System.out.print(b);
                    System.exit(0);
                }

                // Divide num by 2
                num = num / 2;
            }

            // Print the final value of the boolean variable
            System.out.print(b);
        }
    }
} 

Sample Output:

Input a number :  25
false

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to check if a given long integer is a power of 4 using bit manipulation in constant time.
• Write a Java program to verify if a number is a power of 2 using a single bitwise operation.
• Write a Java program to check if a number is both a power of 2 and a perfect square.
• Write a Java program to determine if a number is a power of 2 and count the number of right shifts needed to reduce it to 1.

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Compute xⁿ % y where x, y and n are all 32bit integers.
Next: Generate a crc32 checksum of a given string or byte array.