Check if Number is Power of Two in DSA Typescript - Execution Trace

Concept Flow - Check if Number is Power of Two

Start with number n

↓

Check if n <= 0?

Yes→Return False

No↓

Check if (n & (n-1)) == 0?

Yes→Return True

No↓

Return False

Start with the number, reject non-positive numbers, then use bitwise AND between n and n-1 to check if only one bit is set.

Execution Sample

DSA Typescript

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

This function returns true if n is a power of two, false otherwise.

Execution Table

Step	Operation	Input n	Check n <= 0	Compute n & (n-1)	Result	Return Value
1	Input number	8	No	8 & 7 = 0	True	true
2	Input number	10	No	10 & 9 = 8	False	false
3	Input number	1	No	1 & 0 = 0	True	true
4	Input number	0	Yes	-	-	false
5	Input number	-4	Yes	-	-	false

💡 Stops after returning true or false based on bitwise check or non-positive check.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
n	-	8	10	1	0	-4
n <= 0	-	false	false	false	true	true
n & (n-1)	-	0	8	0	-	-
Return Value	-	true	false	true	false	false

Key Moments - 3 Insights

Why do we check if n <= 0 before the bitwise operation?

Because powers of two are positive numbers. The execution_table rows 4 and 5 show that if n is zero or negative, the function returns false immediately without bitwise checks.

Why does (n & (n-1)) == 0 mean n is a power of two?

Because powers of two have only one '1' bit in binary. Subtracting 1 flips that bit and all lower bits, so ANDing them results in zero. See execution_table rows 1 and 3 where this condition is true.

What happens if n is 1?

Since 1 is 2^0, it is a power of two. The bitwise check (1 & 0) equals 0, so the function returns true as shown in execution_table row 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when n = 10?

A undefined

B true

C false

D error

💡 Hint

Check row 2 in execution_table under 'Return Value'

At which step does the function return false because n <= 0?

A Step 4

B Step 1

C Step 3

D Step 5

💡 Hint

Look at execution_table rows where 'Check n <= 0' is Yes and return value is false

If n = 16, what would (n & (n-1)) evaluate to?

A 15

B 0

C 16

D 1

💡 Hint

Recall that for powers of two, n & (n-1) equals 0 as shown in execution_table rows 1 and 3

Concept Snapshot

Check if number n is power of two:
- Return false if n <= 0
- Use bitwise AND: (n & (n-1)) == 0 means true
- Only one bit set in n means power of two
- Works for positive integers including 1
- Simple and fast bitwise trick

Full Transcript

This concept checks if a number is a power of two using a bitwise trick. First, it rejects zero or negative numbers because powers of two are positive. Then it uses the expression (n & (n-1)) which clears the lowest set bit. If the result is zero, it means only one bit was set in n, so n is a power of two. The function returns true in that case, otherwise false. Examples include 8 and 1 returning true, 10 and 0 returning false. This method is efficient and uses simple bitwise operations.

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)