Check if Number is Power of Two in DSA Javascript - 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, first check if it is positive. Then use bitwise AND between n and n-1 to decide if it is a power of two.

Execution Sample

DSA Javascript

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

This code checks if a number is a power of two using bitwise operations.

Execution Table

Step	Operation	n	n-1	n & (n-1)	Result	Return Value
1	Input number	8	7	N/A	N/A	N/A
2	Check if n <= 0	8	7	N/A	False (8 > 0)	Continue
3	Calculate n & (n-1)	8 (1000)	7 (0111)	0 (0000)	0	Continue
4	Check if n & (n-1) == 0	8	7	0	True	Return True
5	End	8	7	0	True	True

💡 n & (n-1) equals 0 means n is a power of two, so return True

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
n	8	8	8	8
n-1	N/A	7	7	7
n & (n-1)	N/A	N/A	0	0
Return Value	N/A	Continue	Continue	True

Key Moments - 3 Insights

Why do we check if n <= 0 first?

Because powers of two are positive numbers. The check at Step 2 in execution_table ensures we don't process zero or negative numbers.

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. This is shown in Step 3 and 4.

What happens if n is not a power of two?

Then n & (n-1) will not be zero, so the function returns false. This is implied by the else branch after Step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of n & (n-1) at Step 3 for n=8?

A 7

B 8

C 0

D 1

💡 Hint

Check the 'n & (n-1)' column in Step 3 of execution_table

At which step does the function decide to return True?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Return Value' column and the 'Result' column in execution_table

If n was 10 instead of 8, what would n & (n-1) be at Step 3?

A 2

B 8

C 10

D 0

💡 Hint

Calculate 10 & 9 in binary and check the 'n & (n-1)' logic from execution_table

Concept Snapshot

Check if number n is power of two:
- Return false if n <= 0
- Use bitwise AND: n & (n-1)
- If result is 0, n is power of two
- Otherwise, not a power of two
- Runs in O(1) time

Full Transcript

This concept checks if a number is a power of two using a simple bitwise trick. First, it ensures the number is positive. Then it uses the fact that powers of two have only one bit set in binary. By doing n & (n-1), if the result is zero, it means n is a power of two. The execution table shows step-by-step how the variables change and when the function returns true or false.

Practice

1. Which of the following best describes a number that is a power of two?

easy

A. It is any even number greater than zero.

B. It is any number divisible by 3.

C. It can be written as 2 raised to an integer exponent (e.g., 2^3 = 8).

D. It is a number that ends with digit 2.

Solution

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

   A power of two is a number that can be expressed as 2 raised to some integer exponent, like 2^0=1, 2^1=2, 2^2=4, etc.

2. Step 2: Compare options with the definition

   Only It can be written as 2 raised to an integer exponent (e.g., 2^3 = 8). correctly describes this. Options A, C, and D do not match the definition.

3. Final Answer:

   It can be written as 2 raised to an integer exponent (e.g., 2^3 = 8). -> 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 even numbers are powers of two
• Confusing divisibility by 3 with powers of two
• Assuming number ending with 2 is power of two

2. Which JavaScript expression correctly checks if a number n is a power of two using bitwise operations?

easy

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

B. n | (n - 1) === 0

C. n ^ (n - 1) === 0

D. n & (n + 1) === 0

Solution

1. Step 1: Understand bitwise check for power of two

   A number that is a power of two has only one bit set. The expression n & (n - 1) clears the lowest set bit. If the result is zero, it means only one bit was set.

2. Step 2: Analyze each option

   n & (n - 1) === 0 uses the correct expression. Options B, C, and D use incorrect bitwise operators or operands.

3. Final Answer:

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

4. Quick Check:

   Bitwise AND with n-1 equals zero means 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
• Using n + 1 instead of n - 1
• Not comparing result to zero

3. What is the output of the following JavaScript code?

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

medium

A. false\nfalse

B. false\ntrue

C. true\ntrue

D. true\nfalse

Solution

1. Step 1: Evaluate isPowerOfTwo(16)

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

2. Step 2: Evaluate isPowerOfTwo(18)

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

3. Final Answer:

   true\nfalse -> Option D

4. Quick Check:

   16 is power of two: true, 18 is not: false [OK]

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

Common Mistakes:

• Assuming all even numbers return true
• Forgetting to check n > 0
• Misunderstanding bitwise AND result

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

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

medium

A. Using bitwise OR instead of AND

B. Not checking if n is positive

C. Missing parentheses around (n & (n - 1))

D. Using subtraction instead of addition

Solution

1. Step 1: Test with edge case n=0

   0 & (0 - 1) = 0 & (-1) = 0 === 0 returns true, but 0 is not a power of two.

2. Step 2: Analyze options

   The function lacks n > 0 check. Not checking if n is positive identifies this. No OR used (B wrong), parentheses not required due to operator precedence (C wrong), subtraction is correct (D wrong).

3. Final Answer:

   Not checking if n is positive -> Option B

4. Quick Check:

   n > 0 && (n & (n-1)) === 0 [OK]

Hint: Include n > 0 check for power of two validation [OK]

Common Mistakes:

• Ignoring operator precedence
• Not checking if number is positive
• Using wrong bitwise operators

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

hard

A. nums.filter(n => n > 0 && (n & (n - 1)) === 0)

B. nums.filter(n => n % 2 === 0)

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

D. nums.filter(n => n > 0 && (n | (n - 1)) === 0)

Solution

1. Step 1: Understand filtering condition for power of two

   We need to keep numbers greater than zero where n & (n - 1) === 0 is true.

2. Step 2: Evaluate each filter condition

   nums.filter(n => n > 0 && (n & (n - 1)) === 0) correctly uses this condition. nums.filter(n => n % 2 === 0) filters even numbers, which is incorrect. Options C and D use wrong bitwise operations.

3. Final Answer:

   nums.filter(n => n > 0 && (n & (n - 1)) === 0) -> Option A

4. Quick Check:

   Filter with bitwise AND and n > 0 [OK]

Hint: Filter with n > 0 and n & (n-1) === 0 to find powers of two [OK]

Common Mistakes:

• Filtering only even numbers
• Using wrong bitwise operators
• Not checking for positive numbers