Check if Number is Power of Two in DSA Typescript - 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 because they equal 2⁰, 2¹, 2², 2³, and 2⁴ respectively. This check helps in many computer tasks where powers of two have special meaning. It is a simple yes or no question about the number's form.

Why it matters

Many computer systems and algorithms work best or only work correctly when numbers are powers of two. For example, memory sizes, data alignment, and efficient calculations often rely on powers of two. Without this check, programs might run slower, use more memory, or even fail. Knowing if a number is a power of two helps optimize and avoid errors in software and hardware.

Where it fits

Before learning this, you should understand basic number properties and binary numbers. After this, you can explore bitwise operations, optimization techniques, and algorithms that use powers of two like binary search or memory management.

Mental Model

Core Idea

A number is a power of two if it has exactly one '1' bit 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 -> power of two

  Number: 10
  Binary: 00001010
  Two '1' bits -> not a power of two

Build-Up - 7 Steps

1

Foundation

Understanding Powers of Two

Concept: Learn what powers of two are and how to recognize them.

A power of two is any number that can be written as 2 raised to an integer exponent (like 2^0=1, 2^1=2, 2^2=4, etc.). These numbers grow by doubling each time. For example, 1, 2, 4, 8, 16, 32, and so on. Recognizing these numbers helps in many computing tasks.

Result

You can list powers of two and identify them by their doubling pattern.

Understanding the basic definition of powers of two sets the foundation for recognizing their unique properties in binary.

2

Foundation

Binary Representation Basics

Concept: Learn how numbers are represented in binary form.

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, decimal 5 is binary 101 (1*2^2 + 0*2^1 + 1*2^0). This helps us see the structure of numbers clearly.

Result

You can convert decimal numbers to binary and understand their bit patterns.

Knowing binary representation is key because the power of two property is easiest to spot in binary.

3

Intermediate

One '1' Bit Means Power of Two

🤔Before reading on: do you think a power of two has multiple '1' bits or just one in binary? Commit to your answer.

Concept: A power of two has exactly one '1' bit in its binary form.

Look at the binary form of powers of two: 1 (1), 2 (10), 4 (100), 8 (1000). Each has only one '1' bit. Numbers like 3 (11) or 6 (110) have more than one '1' bit, so they are not powers of two.

Result

You can identify powers of two by counting '1' bits in binary.

Understanding this bit pattern simplifies the check to a simple count of '1's.

4

Intermediate

Bitwise Trick to Check Power of Two

🤔Before reading on: do you think checking if n & (n-1) equals zero is a valid way to find powers of two? Commit to yes or no.

Concept: Using bitwise AND between n and n-1 to check if a number is a power of two.

If n is a power of two, its binary form has one '1'. Subtracting 1 flips all bits after that '1'. Doing n & (n-1) clears the lowest '1' bit. If the result is zero, n had only one '1' bit, so it is a power of two. For example, 8 (1000) & 7 (0111) = 0.

Result

You can quickly check powers of two with a single bitwise operation.

This trick is efficient and widely used in programming for fast checks.

5

Intermediate

Handling Edge Cases and Zero

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

Concept: Recognizing that zero and negative numbers are not powers of two and must be handled separately.

Zero (0) has no '1' bits and is not a power of two. Negative numbers in two's complement form have different bit patterns and are also not powers of two. So, the check must ensure the number is positive before applying the bitwise trick.

Result

You avoid false positives by excluding zero and negatives.

Knowing these exceptions prevents bugs and incorrect results in real programs.

6

Advanced

TypeScript Implementation with Bitwise Check

🤔Before reading on: do you think the function should return false for zero and negative inputs? Commit to yes or no.

Concept: Writing a complete TypeScript function that uses the bitwise trick and handles edge cases.

function isPowerOfTwo(n: number): boolean { if (n <= 0) return false; return (n & (n - 1)) === 0; } // Example usage: // isPowerOfTwo(8) returns true // isPowerOfTwo(10) returns false // isPowerOfTwo(0) returns false // isPowerOfTwo(-2) returns false

Result

The function correctly identifies powers of two and rejects others.

Combining bitwise logic with input validation creates a robust and efficient solution.

7

Expert

Why Bitwise Check is Fast and Reliable

🤔Before reading on: do you think the bitwise check is faster than looping or dividing repeatedly? Commit to yes or no.

Concept: Understanding why the bitwise method is preferred in performance-critical code.

The bitwise AND operation runs in constant time, directly on the binary representation. Other methods like loops or division take more steps and time. This makes the bitwise check very fast, especially for large numbers. It also avoids errors from floating-point operations or loops.

Result

You appreciate why this method is standard in systems programming and libraries.

Knowing the performance and reliability benefits explains why experts always use this approach.

Under the Hood

The bitwise check works because numbers are stored in binary form. When you subtract 1 from a power of two, the single '1' bit flips to '0' and all lower bits flip to '1'. Doing a bitwise AND between the original number and this new number clears the only '1' bit if it was a power of two, resulting in zero. This relies on how binary subtraction and bitwise operations manipulate bits directly in the processor.

Why designed this way?

This method was designed to leverage the binary nature of computers for speed and simplicity. Early computer scientists noticed this pattern and created this trick to avoid slower arithmetic or loops. Alternatives like repeated division or counting bits are slower or more complex. The bitwise approach is minimal, fast, and easy to implement in hardware and software.

  n (power of two):    00010000 (16 decimal)
  n - 1:               00001111 (15 decimal)
  n & (n - 1):         00000000 (0 decimal)

  Result zero means n is power of two.

Myth Busters - 3 Common Misconceptions

Quick: Is zero a power of two? Commit to yes or no before reading on.

Common Belief: Zero is a power of two because 2 raised to zero is one, and zero is close to that.

Reality: Zero is not a power of two. 2 raised to zero equals one, not zero.

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

Quick: Does the bitwise check work for negative numbers? Commit to yes or no.

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

Reality: Negative numbers are not powers of two, and the bitwise check can give wrong results if negatives are not excluded.

Why it matters: Failing to exclude negatives leads to false positives and bugs in software.

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

Common Belief: Counting '1' bits is the only way to check if a number is a power of two.

Reality: The bitwise trick n & (n-1) === 0 is a faster and simpler method than counting bits.

Why it matters: Using slower methods can reduce performance in critical applications.

Expert Zone

1

The bitwise check only works for positive integers; zero and negatives must be filtered out first.

2

In some languages or systems, integer overflow or non-integer inputs can cause unexpected results, so input validation is crucial.

3

The method assumes two's complement binary representation, which is standard but worth knowing for low-level programming.

When NOT to use

Avoid this method when working with floating-point numbers, non-integers, or very large numbers that exceed integer limits. In such cases, use logarithmic checks or specialized libraries for arbitrary precision.

Production Patterns

This check is used in memory allocation to ensure block sizes are powers of two, in graphics programming for texture sizes, and in algorithms like FFT that require power-of-two input sizes. It is also common in embedded systems and performance-critical code.

Connections

Bitwise Operations

Builds-on

Understanding this check deepens knowledge of bitwise AND and subtraction, foundational for many low-level algorithms.

Logarithms

Alternative method

Knowing logarithms helps verify powers of two by checking if log base 2 is an integer, connecting math and binary concepts.

Electrical Engineering - Signal Processing

Shared pattern

Powers of two appear in signal sampling rates and filter designs, showing how this concept crosses from computing to physical systems.

Common Pitfalls

#1 Not excluding zero and negative numbers before the bitwise check.

Wrong approach:

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

Correct approach:

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

Root cause:

Assuming the bitwise trick works for all integers without input validation.

#2 Using loops or division to check powers of two instead of bitwise operations.

Wrong approach:

function isPowerOfTwo(n: number): boolean {
if (n <= 0) return false;
while (n % 2 === 0) {
n = n / 2;
}
return n === 1;
}

Correct approach:

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

Root cause:

Not knowing the efficient bitwise method and relying on slower arithmetic.

#3 Checking floating-point numbers without integer validation.

Wrong approach:

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

Correct approach:

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

Root cause:

Ignoring that bitwise operations only work correctly on integers.

Key Takeaways

A power of two has exactly one '1' bit in its binary form, making it easy to identify.

The bitwise operation n & (n - 1) equals zero only for powers of two, providing a fast check.

Always exclude zero, negative numbers, and non-integers before applying the bitwise check.

This method is faster and more reliable than loops or division for checking powers of two.

Understanding this concept connects binary math with practical programming and hardware design.

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)