Check if Number is Power of Two in DSA Javascript - Deep Dive

Overview - Check if Number is Power of Two

What is it?

Checking if a number is a power of two means finding out if it can be written as 2 raised to some whole number. For example, 1, 2, 4, 8, and 16 are powers of two. This is useful in computing because many systems work best with sizes that are powers of two. The task is to write a method that tells if a given number fits this pattern.

Why it matters

Many computer systems and algorithms rely on powers of two for efficiency, like memory allocation and data structures. Without this check, programs might waste resources or run slower. Knowing if a number is a power of two helps optimize performance and avoid errors in these systems.

Where it fits

Before this, you should understand basic number properties and binary numbers. After this, you can learn about bitwise operations and how they speed up calculations in algorithms.

Mental Model

Core Idea

A number is a power of two if it has exactly one '1' in its binary form.

Think of it like...

Imagine a row of light switches where 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.

Binary representation example:

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

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

Build-Up - 6 Steps

1

Foundation

Understanding Powers of Two

Concept: Introduce what powers of two are and how they look in decimal and binary.

Powers of two are numbers like 1, 2, 4, 8, 16, etc. Each is 2 multiplied by itself some number of times. In binary, these numbers have a single '1' followed by zeros. For example, 4 in binary is 100, and 8 is 1000.

Result

Learner can identify powers of two by their decimal and binary forms.

Understanding the binary pattern of powers of two is key to checking them efficiently.

2

Foundation

Binary Representation Basics

Concept: Explain how numbers are represented in binary and how to read them.

Every number can be written in binary using only 0s and 1s. Each position represents a power of two, starting from the right with 2^0. For example, 5 is 101 in binary (4 + 0 + 1).

Result

Learner can convert small numbers to binary and understand bit positions.

Knowing binary helps see why powers of two have only one '1' bit.

3

Intermediate

Counting '1' Bits to Check Power

🤔Before reading on: do you think counting all '1' bits is the fastest way to check if a number is a power of two? Commit to yes or no.

Concept: Check if a number has exactly one '1' bit by counting bits.

One way is to convert the number to binary and count how many '1's it has. If exactly one, it's a power of two. For example, 8 (1000) has one '1', so true; 10 (1010) has two '1's, so false.

Result

You can determine power of two by counting bits.

Counting bits works but can be slow for large numbers; it shows the core property clearly.

4

Intermediate

Using Bitwise AND Trick

🤔Before reading on: do you think the expression (n & (n - 1)) === 0 works for all numbers to check power of two? Commit to yes or no.

Concept: Use a fast bitwise operation to check power of two.

If n is a power of two, then n & (n - 1) equals zero. This works because subtracting 1 flips the rightmost '1' bit and all bits after it. ANDing with n clears that bit, so if only one '1' existed, result is zero. Example: 8 & 7 = 1000 & 0111 = 0000.

Result

Fast check for power of two using bitwise AND.

This trick is efficient and elegant, used in many systems for quick checks.

5

Advanced

Handling Edge Cases and Zero

🤔Before reading on: do you think zero is a power of two? Commit to yes or no.

Concept: Understand special cases like zero and negative numbers.

Zero is not a power of two because it has no '1' bits. Negative numbers in two's complement form have many '1's and are not powers of two. So, checks must exclude zero and negatives explicitly.

Result

Correctly exclude zero and negatives from power of two results.

Handling edge cases prevents bugs and incorrect results in real programs.

6

Expert

Bitwise Check in JavaScript with Explanation

🤔Before reading on: do you think JavaScript's bitwise operators always work correctly for large numbers? Commit to yes or no.

Concept: Implement and explain the bitwise check in JavaScript, noting language specifics.

JavaScript bitwise operators work on 32-bit signed integers. For numbers larger than 2^31-1, bitwise operations may give unexpected results. The common check is: function isPowerOfTwo(n) { return n > 0 && (n & (n - 1)) === 0; } This works well for typical integer ranges but be cautious with very large numbers.

Result

A reliable JavaScript function to check power of two within 32-bit integer range.

Knowing JavaScript's bitwise limits avoids subtle bugs in large number checks.

Under the Hood

The bitwise AND operation compares each bit of two numbers. When you do n & (n - 1), it clears the rightmost '1' bit in n. If n had only one '1' bit, this operation results in zero. This works because subtracting 1 flips bits after the rightmost '1', so ANDing removes that bit. This is a fast, low-level way to test the unique bit pattern of powers of two.

Why designed this way?

This method was designed to optimize performance by using simple bitwise operations instead of loops or counting bits. Early computer systems needed fast checks for powers of two for memory and processor efficiency. Alternatives like counting bits are slower, so this trick became a standard.

n in binary:      00001000 (8)
n - 1 in binary:  00000111 (7)
AND result:       00000000 (0)

If result is 0 and n > 0, n is power of two.

Myth Busters - 3 Common Misconceptions

Quick: Is zero considered a power of two? Commit to yes or no.

Common Belief: Zero is a power of two because it is 2 raised to the power of zero.

Reality: Zero is not a power of two; 2^0 equals 1, not zero.

Why it matters: Treating zero as power of two causes incorrect program behavior and logic errors.

Quick: Does the expression (n & (n - 1)) === 0 work for negative numbers? Commit to yes or no.

Common Belief: The bitwise trick works for all integers, including negatives.

Reality: Negative numbers are not powers of two, and the bitwise trick can give false positives due to two's complement representation.

Why it matters: Failing to exclude negatives leads to wrong results and bugs in applications.

Quick: Is counting the number of '1' bits the fastest way to check power of two? Commit to yes or no.

Common Belief: Counting all '1' bits is the best method to check if a number is a power of two.

Reality: Counting bits is slower than the bitwise AND trick, especially for large numbers.

Why it matters: Using slower methods can degrade performance in critical systems.

Expert Zone

1

JavaScript bitwise operators work on 32-bit signed integers, so very large numbers may not be checked correctly.

2

The bitwise trick only works for positive integers; zero and negatives must be handled separately.

3

In some systems, floating-point numbers close to powers of two require special handling to avoid false positives.

When NOT to use

Avoid using bitwise checks for non-integer or very large numbers beyond 32-bit range. Instead, use logarithmic checks or specialized libraries for big integers.

Production Patterns

Used in memory allocation, graphics programming, and network packet sizing where sizes must be powers of two. Also common in algorithms like FFT and hashing for performance optimization.

Connections

Bitwise Operations

Builds-on

Understanding bitwise operations is essential to grasp the efficient power of two check.

Logarithms

Alternative method

Using logarithms can check powers of two by verifying if log base 2 is an integer, connecting math and computing.

Electrical Engineering - Signal Processing

Similar pattern recognition

Recognizing single active signals in circuits parallels detecting single '1' bits in numbers, showing cross-domain pattern matching.

Common Pitfalls

#1 Not excluding zero leads to false positives.

Wrong approach:

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

Correct approach:

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

Root cause:

Assuming the bitwise trick alone is sufficient without checking if n is positive.

#2 Applying bitwise check to negative numbers causes wrong results.

Wrong approach:

function isPowerOfTwo(n) {
return n > 0 || (n & (n - 1)) === 0;
}

Correct approach:

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

Root cause:

Misunderstanding that negative numbers must be excluded explicitly.

#3 Using bitwise operators on very large numbers without caution.

Wrong approach:

function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
} // for n = 5000000000

Correct approach:

function isPowerOfTwo(n) {
if (n <= 0) return false;
if (n > 0x7FFFFFFF) return Number.isInteger(Math.log2(n)) && Math.log2(n) % 1 === 0;
return (n & (n - 1)) === 0;
}

Root cause:

Ignoring JavaScript's 32-bit limit on bitwise operations.

Key Takeaways

A number is a power of two if it has exactly one '1' bit in binary.

The bitwise AND trick (n & (n - 1)) === 0 is a fast way to check powers of two.

Always exclude zero and negative numbers explicitly when checking powers of two.

JavaScript bitwise operations work on 32-bit signed integers, so be careful with large numbers.

Understanding this concept helps optimize many computing tasks involving memory and performance.

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