Check if Number is Power of Two in DSA Typescript

Mental Model

A number is a power of two if it can be divided by two repeatedly until it becomes one, without any remainder.

Analogy: Imagine folding a paper in half repeatedly. If you can fold it exactly until only one layer remains, the number of folds is a power of two.

Number: 8
8 -> 4 -> 2 -> 1
Check if each step divides evenly by 2 until 1

Dry Run Walkthrough

Input: number = 8

Goal: Determine if 8 is a power of two

Step 1: Check if number is less than or equal to 0

number = 8

Why: Negative numbers and zero cannot be powers of two

Step 2: Check if number & (number - 1) equals 0

8 in binary: 1000
7 in binary: 0111
8 & 7 = 0000

Why: A power of two has only one '1' bit, so this bitwise trick confirms it

Step 3: Return true because condition is met

Result: true

Why: The number 8 is confirmed as a power of two

Result:

Result: true

Annotated Code

DSA Typescript

class PowerOfTwoChecker {
  static isPowerOfTwo(n: number): boolean {
    if (n <= 0) return false; // negative or zero check
    return (n & (n - 1)) === 0; // bitwise check for power of two
  }
}

// Driver code
const number = 8;
const result = PowerOfTwoChecker.isPowerOfTwo(number);
console.log(`Result: ${result}`);

if (n <= 0) return false;

Exclude zero and negative numbers as they cannot be powers of two

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

Use bitwise AND to check if only one bit is set in n

Output

Result: true

Complexity Analysis

Time: O(1) because the bitwise operation runs in constant time regardless of input size

Space: O(1) because no extra space is used beyond variables

vs Alternative: Compared to dividing repeatedly by 2 (O(log n)), this bitwise method is faster and simpler

Edge Cases

number = 0

Returns false because zero is not a power of two

DSA Typescript

if (n <= 0) return false;

number = 1

Returns true because 1 is 2^0, a power of two

DSA Typescript

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

number = -4

Returns false because negative numbers are not powers of two

DSA Typescript

if (n <= 0) return false;

When to Use This Pattern

When you need to quickly check if a number is a power of two, use the bitwise AND trick because it efficiently tests the single set bit property.

Common Mistakes

Mistake: Trying to check powers of two by dividing repeatedly without handling zero or negative numbers
Fix: Add a check to return false immediately if the number is less than or equal to zero

Mistake: Using loops instead of the bitwise trick, making the solution slower
Fix: Use the bitwise expression (n & (n - 1)) === 0 for constant time check

Summary

Checks if a number has exactly one bit set, meaning it is a power of two.

Use when you need a fast and simple way to verify powers of two.

The key insight is that powers of two have only one '1' bit in binary, so n & (n-1) clears that bit to zero.

Practice

1. What does it mean if a number is a power of two?

easy

A. It is divisible by 3

B. It is always an odd number

C. It can be written as 2 raised to some integer exponent

D. It is a prime number

Solution

1. Step 1: Understand the definition of power of two

   A number is a power of two if it equals 2 raised to an integer exponent, like 2^0=1, 2^1=2, 2^2=4, etc.

2. Step 2: Check other options

   Odd numbers, divisibility by 3, or primality do not define powers of two.

3. Final Answer:

   It can be written as 2 raised to some integer exponent -> Option C

4. Quick Check:

   Power of two = 2^n [OK]

Hint: Power of two means 2 multiplied by itself n times [OK]

Common Mistakes:

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

2. Which of the following TypeScript expressions correctly checks if a number n is a power of two using bitwise operations?

easy

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

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

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

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

Solution

1. Step 1: Understand the 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 each option

   return n > 0 && (n & (n - 1)) === 0; uses the correct bitwise AND with (n-1). Options A, B, and C use incorrect bitwise operators or operands.

3. Final Answer:

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

4. Quick Check:

   Bitwise AND with (n-1) = 0 means power of two [OK]

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

Common Mistakes:

• Using bitwise OR instead of AND
• Using (n + 1) instead of (n - 1)
• Forgetting to check n > 0

3. What will be the output of this TypeScript code?

function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}
console.log(isPowerOfTwo(16));
console.log(isPowerOfTwo(18));

medium

A. true true

B. false true

C. false false

D. true false

Solution

1. Step 1: Check isPowerOfTwo(16)

   16 in binary is 10000. 16 & 15 (01111) = 0, so returns true.

2. Step 2: Check isPowerOfTwo(18)

   18 in binary is 10010. 18 & 17 (10001) = 16 (not zero), so returns false.

3. Final Answer:

   true false -> Option D

4. Quick Check:

   16 is power of two, 18 is not [OK]

Hint: Check bitwise AND with (n-1) to confirm power of two [OK]

Common Mistakes:

• Assuming 18 is power of two because it's even
• Ignoring the n > 0 condition
• Misreading bitwise AND results

4. Identify the error in this TypeScript function that checks if a number is a power of two:

function checkPower(n: number): boolean {
  return (n & (n - 1)) === 0;
}

medium

A. Missing check for n > 0 to avoid false positives

B. Incorrect bitwise operator used

C. Function should return number, not boolean

D. Parentheses are misplaced

Solution

1. Step 1: Analyze the function logic

   The function uses bitwise AND correctly but does not check if n is positive.

2. Step 2: Understand why n > 0 is needed

   Without n > 0, input 0 returns true incorrectly because 0 & -1 = 0.

3. Final Answer:

   Missing check for n > 0 to avoid false positives -> Option A

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Always check n > 0 before bitwise power of two test [OK]

Common Mistakes:

• Ignoring zero or negative inputs
• Assuming bitwise alone is enough
• Misunderstanding bitwise AND behavior

5. You want to filter an array of numbers to keep only those that are powers of two. Which TypeScript code snippet correctly does this?

const numbers = [0, 1, 2, 3, 4, 5, 8, 16, 18];
const powersOfTwo = numbers.filter(n => ???);
console.log(powersOfTwo);

hard

A. n >= 0 && (n | (n - 1)) === 0

B. n > 0 && (n & (n - 1)) === 0

C. n > 0 && (n & (n + 1)) === 0

D. n !== 0 && (n ^ (n - 1)) === 0

Solution

1. Step 1: Understand the filter condition

   We want to keep numbers that are powers of two, so the condition must check n > 0 and bitwise AND with (n-1) equals zero.

2. Step 2: Evaluate each option

   n > 0 && (n & (n - 1)) === 0 correctly uses the standard power of two check. Options B, C, and D use incorrect bitwise operations or conditions.

3. Final Answer:

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

4. Quick Check:

   Filter with bitwise AND and n > 0 [OK]

Hint: Filter with n > 0 and n & (n-1) === 0 [OK]

Common Mistakes:

• Using bitwise OR or XOR instead of AND
• Not checking n > 0
• Using (n + 1) instead of (n - 1)