Check if Number is Power of Two in DSA Javascript

Mental Model

A number is a power of two if it can be made by multiplying 2 by itself some times, like 2, 4, 8, 16, etc. We can check this by seeing if only one bit is set in its binary form.

Analogy: Imagine you have a row of light switches, and only one switch is turned on at a time. If exactly one switch is on, the number is a power of two. If more or none are on, it is not.

Number: 8
Binary: 1 0 0 0
Only one '1' bit means power of two

Number: 10
Binary: 1 0 1 0
More than one '1' bit means NOT power of two

Dry Run Walkthrough

Input: number = 8

Goal: Check if 8 is a power of two

Step 1: Check if number is greater than 0

number = 8 (valid input)

Why: Only positive numbers can be powers of two

Step 2: Calculate number & (number - 1): 8 & 7

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

Why: If result is 0, number has only one '1' bit

Step 3: Since result is 0, conclude number is power of two

Result: true

Why: Only one bit set means power of two

Result:

8 is a power of two: true

Annotated Code

DSA Javascript

class PowerOfTwoChecker {
  static isPowerOfTwo(number) {
    if (number <= 0) return false; // reject non-positive numbers
    return (number & (number - 1)) === 0; // check single bit set
  }
}

// Driver code
const number = 8;
const result = PowerOfTwoChecker.isPowerOfTwo(number);
console.log(`${number} is a power of two: ${result}`);

if (number <= 0) return false; // reject non-positive numbers

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

return (number & (number - 1)) === 0; // check single bit set

bitwise check to confirm only one bit is set in number

Output

8 is a power of two: true

Complexity Analysis

Time: O(1) because bitwise operations take constant time regardless of number size

Space: O(1) because no extra memory is used except a few variables

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

Edge Cases

number = 0

Returns false because zero is not a power of two

DSA Javascript

if (number <= 0) return false;

number = 1

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

DSA Javascript

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

number = -4

Returns false because negative numbers are not powers of two

DSA Javascript

if (number <= 0) return false;

When to Use This Pattern

When you see a problem asking if a number is a power of two, reach for the bitwise AND trick because it quickly checks if only one bit is set.

Common Mistakes

Mistake: Checking if number % 2 == 0 repeatedly without stopping at 1
Fix: Stop dividing when number becomes 1 and check if all divisions were exact

Mistake: Not handling zero or negative numbers
Fix: Add a check to return false if number is less than or equal to zero

Summary

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

Use this when you need a fast way to verify powers of two without loops.

The key insight is that powers of two have only one '1' bit, so number & (number - 1) equals zero.

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