Check if Number is Power of Two in DSA Typescript - 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

How can you check if a number is a power of two using bitwise operations?

If a number is a power of two, it has exactly one '1' bit in its binary form. So, n & (n - 1) equals 0 for powers of two (and n > 0).

beginner

TypeScript code snippet: What does this function do?

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

This function checks if the input number n is a power of two by verifying n is positive and that n & (n - 1) equals zero.

beginner

Why must we check that n > 0 when checking if n is a power of two?

Because zero and negative numbers are not powers of two, and the bitwise check alone would incorrectly say zero passes since 0 & (0 - 1) = 0.

beginner

What is the binary pattern of a power of two number?

It has exactly one '1' bit followed by zeros. For example, 8 in binary is 1000, which has one '1' and three '0's.

Which of these numbers is a power of two?

A 16

B 18

C 20

D 22

16 is 2^4, so it is a power of two. The others are not powers of two.

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

A If n is a power of two

B If n is even

C If n is prime

D If n is negative

n & (n - 1) equals zero only if n is a power of two.

Why do we need to check n > 0 before using n & (n - 1)?

A Because negative numbers are powers of two

B Because zero is a power of two

C Because zero and negatives are not powers of two and bitwise check fails for them

D Because n must be odd

Zero and negative numbers are not powers of two, so we exclude them explicitly.

What is the output of isPowerOfTwo(1)?

A false

B true

C undefined

D error

1 is 2^0, so it is a power of two.

Which binary number represents a power of two?

A 1010

B 1100

C 1111

D 1000

1000 has exactly one '1' bit, so it is a power of two.

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 bits.

Write a simple TypeScript function to check if a number is a power of two and explain each step.

Use bitwise AND and remember to exclude zero and negatives.

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)