Why Check if Number is Power of Two in DSA Java?

The Big Idea

Discover a tiny trick that saves you from long, boring division checks!

The Scenario

Imagine you have a big list of numbers and you want to find out which ones are powers of two, like 1, 2, 4, 8, 16, and so on. Doing this by hand means dividing each number by 2 again and again until you reach 1 or a number that is not divisible by 2.

The Problem

This manual method is slow and boring. It's easy to make mistakes, especially with big numbers. You might lose track of divisions or forget to check if the number is exactly 1 at the end. This wastes time and causes errors.

The Solution

Using a simple check with bits, we can quickly tell if a number is a power of two. This method uses the fact that powers of two have only one '1' bit in their binary form. It's fast, clean, and never makes mistakes.

Before vs After

✗ Before

boolean isPowerOfTwo(int number) {
  while (number > 1) {
    if (number % 2 != 0) return false;
    number = number / 2;
  }
  return number == 1;
}

✓ After

boolean isPowerOfTwo(int number) {
  return number > 0 && (number & (number - 1)) == 0;
}

What It Enables

This lets you quickly and reliably check powers of two, enabling faster programs and easier problem solving.

Real Life Example

In computer memory, sizes are often powers of two. Checking if a size fits this rule helps optimize storage and speed.

Key Takeaways

Manual division to check powers of two is slow and error-prone.

Bitwise check is fast and simple.

Useful in memory management and optimization tasks.

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)