Check if Number is Power of Two in DSA Java - Build from Scratch

Check if Number is Power of Two

📖 Scenario: Imagine you are working with a system that needs to quickly check if a number is a power of two. Powers of two are special numbers like 1, 2, 4, 8, 16, and so on. This check is useful in many computer tasks such as memory allocation and optimization.

🎯 Goal: You will build a simple Java program that checks if a given number is a power of two using a straightforward method.

📋 What You'll Learn

Create an integer variable named number with the value 16

Create a boolean variable named isPowerOfTwo to store the result

Use a loop to check if number can be divided by 2 repeatedly until it becomes 1

Print the value of isPowerOfTwo to show if the number is a power of two

💡 Why This Matters

🌍 Real World

Checking if a number is a power of two is useful in computer memory management and optimizing algorithms.

💼 Career

Understanding this concept helps in roles involving system programming, embedded systems, and performance optimization.

1

Create the number variable

Create an integer variable called number and set it to 16.

DSA Java

# Your code here

Hint

Use int number = 16; inside the main method.

2

Add a boolean variable to store the result

Create a boolean variable called isPowerOfTwo and set it to true initially.

DSA Java

public class PowerOfTwo {
    public static void main(String[] args) {
        int number = 16;
        // Your code here
    }
}

Hint

Use boolean isPowerOfTwo = true; to start assuming the number is a power of two.

3

Check if the number is a power of two using a loop

Use a while loop to divide number by 2 repeatedly while number is greater than 1. Inside the loop, if number % 2 != 0, set isPowerOfTwo to false and break the loop. Otherwise, divide number by 2.

DSA Java

public class PowerOfTwo {
    public static void main(String[] args) {
        int number = 16;
        boolean isPowerOfTwo = true;
        // Your code here
    }
}

Hint

Use a temporary variable to keep dividing the number by 2 until it becomes 1 or you find it is not divisible by 2.

4

Print the result

Print the value of isPowerOfTwo using System.out.println(isPowerOfTwo);.

DSA Java

public class PowerOfTwo {
    public static void main(String[] args) {
        int number = 16;
        boolean isPowerOfTwo = true;
        int temp = number;
        while (temp > 1) {
            if (temp % 2 != 0) {
                isPowerOfTwo = false;
                break;
            }
            temp = temp / 2;
        }
        // Your code here
    }
}

Hint

Use System.out.println(isPowerOfTwo); to show the result.

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It is divisible by 3.

B. It is always an odd number.

C. It has exactly one bit set to 1 in its binary form.

D. It has all bits set to 1 in its binary form.

Solution

1. Step 1: Understand binary representation of powers of two

   A power of two in binary has exactly one '1' bit and the rest are '0's, e.g., 4 is 100.

2. Step 2: Check other options

   Odd numbers and divisibility by 3 do not define powers of two. Having all bits set to 1 is not a power of two.

3. Final Answer:

   It has exactly one bit set to 1 in its binary form. -> Option C

4. Quick Check:

   Power of two = single 1 bit [OK]

Hint: Power of two has only one '1' bit in binary [OK]

Common Mistakes:

• Thinking all odd numbers are powers of two
• Confusing powers of two with numbers having all bits set
• Assuming divisibility by 3 means power of two

2. Which of the following Java code snippets correctly checks if an integer n is a power of two?

easy

A. return (n | (n - 1)) == 0;

B. return (n & (n - 1)) == 0;

C. return (n & (n + 1)) == 0;

D. return (n ^ (n - 1)) == 0;

Solution

1. Step 1: Understand bitwise check for power of two

   The expression n & (n - 1) clears the lowest set bit. For powers of two, this results in zero.

2. Step 2: Analyze other options

   Options A, C, and D use incorrect bitwise operations that do not correctly check power of two.

3. Final Answer:

   return (n & (n - 1)) == 0; -> Option B

4. Quick Check:

   Use n & (n-1) == 0 to check power of two [OK]

Hint: Use n & (n-1) == 0 to check power of two [OK]

Common Mistakes:

• Using OR or XOR instead of AND in bitwise check
• Checking n & (n + 1) which is incorrect
• Not considering zero or negative numbers

3. What is the output of the following Java code?

int n = 16;
boolean result = (n & (n - 1)) == 0;
System.out.println(result);

medium

A. true

B. Compilation error

C. false

D. Runtime exception

Solution

1. Step 1: Calculate n & (n - 1) for n = 16

   16 in binary is 10000, 15 is 01111. Bitwise AND is 00000 (0).

2. Step 2: Compare result to zero

   Since 16 & 15 == 0, the expression is true, so result is true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   16 is power of two, so output is true [OK]

Hint: If n & (n-1) == 0, print true [OK]

Common Mistakes:

• Confusing bitwise AND with OR
• Expecting false for powers of two
• Ignoring parentheses in expression

4. The following Java method is intended to check if a number is a power of two. What is the error?

public static boolean isPowerOfTwo(int n) {
    return (n & n - 1) == 0;
}

medium

A. Method does not handle negative numbers.

B. Using bitwise OR instead of AND.

C. Incorrect return type.

D. Missing parentheses around (n - 1) causing wrong calculation.

Solution

1. Step 1: Identify issue with negative numbers

   For n = Integer.MIN_VALUE (-2147483648), which is 0x80000000 in two's complement, n-1 = 0x7FFFFFFF (Integer.MAX_VALUE), and 0x80000000 & 0x7FFFFFFF == 0, so it incorrectly returns true.

2. Step 2: Rule out other options

   Return type is correct, it uses AND (&), and operator precedence correctly parses as n & (n - 1) (no missing parentheses needed).

3. Final Answer:

   Method does not handle negative numbers. -> Option A

4. Quick Check:

   n > 0 && (n & (n-1)) == 0 [OK]

Hint: Include n > 0 to handle zero and negatives [OK]

Common Mistakes:

• Not checking n > 0 before bitwise operation
• Ignoring negative input handling
• Confusing bitwise AND with OR

5. You want to write a Java method that returns true if a given positive integer n is a power of two, and false otherwise. Which of the following implementations correctly handles all positive integers including 1, and excludes zero and negative numbers?

hard

A. return n >= 0 && (n & (n + 1)) == 0;

B. return (n & (n - 1)) == 0;

C. return n != 0 && (n | (n - 1)) == 0;

D. return n > 0 && (n & (n - 1)) == 0;

Solution

1. Step 1: Check for positive number condition

   Zero and negative numbers are not powers of two, so n > 0 is required.

2. Step 2: Use bitwise check for power of two

   The expression (n & (n - 1)) == 0 correctly identifies powers of two including 1.

3. Step 3: Analyze other options

   return (n & (n - 1)) == 0; misses positive check, allowing zero. Options C and D use incorrect bitwise operations.

4. Final Answer:

   return n > 0 && (n & (n - 1)) == 0; -> Option D

5. Quick Check:

   Check positive and n & (n-1) == 0 [OK]

Hint: Check n > 0 before bitwise test [OK]

Common Mistakes:

• Not excluding zero and negative numbers
• Using incorrect bitwise operators
• Missing parentheses around (n - 1)