Check if Number is Power of Two in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a number to be a power of two?

A number is a power of two if it can be written as 2 raised to an integer exponent, like 1, 2, 4, 8, 16, etc.

intermediate

Which bitwise operation can quickly check if a number is a power of two?

Using (n & (n - 1)) == 0 checks if n is a power of two, because powers of two have only one bit set.

beginner

Why must we check that the number is greater than zero when checking if it is a power of two?

Because zero and negative numbers are not powers of two, and the bitwise trick works only for positive numbers.

beginner

What is the output of the check for number 16 using the bitwise method?

16 is a power of two, so (16 & 15) == 0 is true, confirming it is a power of two.

beginner

Write the Java condition to check if an integer n is a power of two.

The condition is: n > 0 && (n & (n - 1)) == 0

Which number is NOT a power of two?

A 10

B 16

C 4

D 8

10 is not a power of two because it cannot be expressed as 2 raised to an integer.

What does the expression (n & (n - 1)) == 0 check for?

A If n is zero

B If n is a power of two

C If n is negative

D If n is odd

This expression is true only if n is a power of two (and n > 0).

Why do we check n > 0 before the bitwise test?

A Because zero is a power of two

B Because zero and negatives are powers of two

C Because negative numbers have one bit set

D Because the bitwise test only works for positive numbers

The bitwise trick works only for positive numbers; zero and negatives are excluded.

What is the result of (8 & 7)?

A 7

B 1

C 0

D 8

8 in binary is 1000, 7 is 0111, so 1000 & 0111 = 0000 (0).

Which of these numbers will return true for the power of two check?

A 1

B 3

C 0

D 6

1 is 2^0, so it is a power of two and passes the check.

Explain how to check if a number is a power of two using bitwise operations.

Think about how powers of two look in binary and how subtracting 1 changes the bits.

Describe why the condition n > 0 is necessary when checking if n is a power of two.

Consider what happens if n is zero or negative in the bitwise test.

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)