On this page

Power Detection — Two, Four, Three & Beyond

🤔 Why Power Detection Matters: The Binary Signature

Imagine you're designing a hash table. Most hash tables use a power-of-two size because it lets you replace the expensive modulo operation with a lightning-fast bitmask: hash & (size - 1). But how do you know if a number is a power of two?

This is a fundamental pattern — power detection appears in memory allocators, image processing, error-correcting codes, and countless coding interviews at FAANG companies. And here's the interesting part: different bases need completely different detection strategies.

Let's understand each approach, from the classic bit trick for powers of two to mathematical detection for bases like 3 that have no simple binary pattern.

Tip

💡 The Key Insight: Powers of two have a clean binary signature — exactly one bit set. Powers of four are a subset (the lone bit at an even position). Powers of three? No binary pattern — we use math. Each base needs a different tool!

1. Is Power of Two — The Classic Bit Trick

Problem: Given an integer n, determine if it is a power of two. A number is a power of two if there exists an integer k such that n = 2ᵏ.

Note

🏦 Real-World Analogy: Imagine you're a bank teller counting money. A power of two is like having a single $100 bill — it can't be broken into smaller bills of the same denomination. In binary, each place value is a power of two: 1, 2, 4, 8, 16... A number that has exactly ONE of these place values turned on — that's a power of two. Like having exactly one coin in your pocket, and it's a $2^k denomination.

🤔 Think About It

What does a power of two look like in binary? Let's check:

1  → 0001  (2^0)
2  → 0010  (2^1)
4  → 0100  (2^2)
8  → 1000  (2^3)
16 → 10000 (2^4)

Spot the pattern? Every power of two has EXACTLY ONEbit set to 1. That's the signature! So the problem reduces to: "Does this number have exactly one set bit?"

Brute Force Approach

function isPowerOfTwoBrute(n) {
  if (n <= 0) return false;
  while (n % 2 === 0) n /= 2;
  return n === 1;
}

// n=16 → 8 → 4 → 2 → 1 → true (3 iterations)
// n=6  → 3 → not divisible by 2 → false

✅ This works. But O(log n) time. We can do BETTER — O(1) with a bit trick!

🔍 Real-Time Thinking — What Do I Know?

"I need to check if a number is a power of two. Brute force: repeatedly divide by 2. That's O(log n). But powers of two have a special binary property: exactly one bit is set. So 16 = 10000, 8 = 1000, 4 = 100, 2 = 10, 1 = 1. Now, I know that n & (n-1) clears the lowest set bit. If the number only has ONE set bit, clearing it gives 0. So the check becomes: n > 0 && (n & (n-1)) === 0. Let me verify: 16 & 15 = 10000 & 01111 = 0. Yes! 12 & 11 = 01100 & 01011 = 01000 = 8, not 0. So 12 isn't a power of two. The trick works!"

✨ The Magic: n & (n-1)

Here's where the bit manipulation MAGIC happens. There's a property: subtracting 1 from a number flips the lowest set bit to 0 and all bits to the right to 1. Then ANDing the original with this result clears the lowest set bit.

If only one bit was set, the result is 0 → power of two!

📋 Edge Cases to Consider

n = 0: 0 & (0-1) = 0 & -1 = 0, but 0 is NOT a power of two. The n > 0 check catches this.
n = 1: 1 = 2⁰, which IS a power of two. 1 & 0 = 0 → returns true (after n > 0 check).
n = -8 (negative power of two): -8 in two's complement has many bits set. The n > 0 check returns false.
n = 2^31 (beyond 32-bit signed max): JavaScript bitwise ops only work on 32-bit signed. 2^31 = -2147483648 (overflows). Use BigInt for larger values.
n = Number.MAX_SAFE_INTEGER: Bitwise ops truncate to 32 bits. Not a reliable check for numbers > 2^31-1.

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

// n=16: 16 & 15 = 10000 & 01111 = 00000 = 0 → true  ✓
// n=12:  12 & 11 = 01100 & 01011 = 01000 = 8 → false ✗
// n=0:   n > 0 catches it!

📊 Dry Run — Watch It In Action

Let's trace through isPowerOfTwo(16) and isPowerOfTwo(12):

n	Binary	n-1	n & (n-1)	n > 0	Result
0	0	N/A	N/A	false	False ✗
1	0001	0 (0000)	1 & 0 = 0	true	True ✓
2	0010	1 (0001)	2 & 1 = 0	true	True ✓
16	10000	15 (01111)	16 & 15 = 0	true	True ✓
6	00110	5 (00101)	6 & 5 = 4	true	False ✗
12	01100	11 (01011)	12 & 11 = 8	true	False ✗
-8	...1000	N/A	N/A	false	False ✗

Alternative: n & (-n) === n

Another classic trick: n & (-n) isolates the lowest set bit. For a power of two, that bit IS the number itself!

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

// n=16: 16 & -16 = 16 → true
// n=6:  6 & -6  = 2  → 2 !== 6 → false

Key Insight

🔑 Why n & (-n) works: In two's complement, -n = ~n + 1. The AND of n and -n isolates the rightmost 1-bit. For powers of two, there's only ONE set bit, so the result equals n itself. This trick is also used in Fenwick Trees (Binary Indexed Trees)!

Edge Cases

n ≤ 0? False — the n > 0 check catches negatives and zero
n = 1? True — 1 = 2⁰, it IS a power of two (single bit at position 0)
Very large numbers? JavaScript bitwise ops work on 32-bit signed integers — use BigInt for larger values

Tip

⚡ Interview Tip: The moment you hear "power of two" in an interview, your brain should go INSTANTLY to n > 0 && (n & (n-1)) === 0. Say it out loud: "A power of two has exactly one set bit. n & (n-1) clears the lowest set bit. If the result is zero, it's a power of two." This is THE most well-known bit manipulation trick — know it cold.

PROBLEMPower of Two

Given an integer n, return true if it is a power of two. Use the bitwise approach: n > 0 && (n & (n-1)) == 0.

Loading playground...

2. Is Power of Four — The Mask Technique

Problem: Given an integer n, determine if it is a power of four.

Here's the interesting twist: every power of four is ALSO a power of two (because 4ᵏ = 2²ᵏ). But the reverse is NOT true — 2 and 8 are powers of two but NOT powers of four. So how do we distinguish them?

Note

🎯 Real-World Analogy: Think of powers of four as a subset of powers of two — like how every square number is a specific kind of number. If powers of two are seats in a theater, powers of four are only the EVEN-numbered seats (seat 0, 2, 4, 6...). You first check if there's exactly one person in the theater (power of two), then check if they're sitting in an even-numbered seat (the 0x55555555 mask).

🤔 Binary Pattern of Powers of Four

Let's look at the binary patterns:

4^0 = 1    → 0001  (bit at position 0  — EVEN)
4^1 = 4    → 0100  (bit at position 2  — EVEN)
4^2 = 16   → 10000 (bit at position 4  — EVEN)
4^3 = 64   → 1000000 (bit at position 6 — EVEN)

Compare with powers of two that are NOT powers of four:
2^1 = 2    → 0010  (bit at position 1  — ODD)  ✗
2^3 = 8    → 1000  (bit at position 3  — ODD)  ✗

Pattern spotted! Powers of four have their lone set bit at an EVEN position (0-indexed from LSB). Powers of two that aren't powers of four have their bit at an ODD position.

✨ The Mask: 0x55555555

0x55555555 is a mask with bits set at ALL even positions. In binary: 0101 0101 0101 0101 0101 0101 0101 0101.

If n is a power of two AND (n & 0x55555555) !== 0, then the lone bit is at an even position → power of four!

function isPowerOfFour(n) {
  return n > 0
      && (n & (n - 1)) === 0  // Must be power of two first
      && (n & 0x55555555) !== 0; // Lone bit at even position?
}

// n=4  (100)    → power of two ✓, 100 & 0x55555555 = 100 → True  ✓
// n=16 (10000)  → power of two ✓, 10000 & 0x55555555 = 10000 → True ✓
// n=2  (10)     → power of two ✓, 10 & 0x55555555 = 0 → False ✗
// n=8  (1000)   → power of two ✓, 1000 & 0x55555555 = 0 → False ✗

Alternative: (n-1) % 3 === 0

There's also a mathematical property: if n is a power of four, then (n - 1) % 3 === 0. This works because 4ᵏ = (3+1)ᵏ, and expanding the binomial gives terms all divisible by 3 except the last +1.

function isPowerOfFour(n) {
  return n > 0
      && (n & (n - 1)) === 0
      && (n - 1) % 3 === 0;  // Mathematical check
}

// n=4:  (4-1) % 3 = 3 % 3 = 0 → True
// n=16: (16-1) % 3 = 15 % 3 = 0 → True
// n=2:  (2-1) % 3 = 1 % 3 = 1 → False

Warning

⚠️ Precision Warning: Don't use Math.log(n) / Math.log(4)for power-of-four detection. Floating-point precision can give false results for large numbers (e.g., Math.log(536870912) / Math.log(4)may not be exactly an integer).

Note

📝 Summary: Power of four = Power of two + even-position mask. The 0x55555555 mask is the standard approach in interviews. The (n-1) % 3 trick is a nice bonus to know!

PROBLEMPower of Four

Given an integer n, return true if it is a power of four. Check power of two first, then verify the lone bit is at an even position using 0x55555555.

Loading playground...

3. Is Power of Three — Mathematical Detection

Problem: Given an integer n, determine if it is a power of three.

Now this is where things get INTERESTING. Three is NOT a power of two, so there's no simple bit pattern to check. The binary representation of powers of three (1, 3, 9, 27, 81...) doesn't follow a clean positional pattern. We need to get mathematical.

🤔 The Binary of 3ᵏ is Messy

3^0 = 1      → 00000001
3^1 = 3      → 00000011
3^2 = 9      → 00001001
3^3 = 27     → 00011011
3^4 = 81     → 01010001
3^5 = 243    → 11110011

See? No consistent bit pattern. We can't use the n & (n-1) trick here. Let's look at the mathematical approaches.

✨ The Magic: 3^19 % n === 0

The largest power of three that fits in a 32-bit signed integer is 3¹⁹ = 1,162,261,467. If n is a power of three, then this maximum power MUST be divisible by n:

function isPowerOfThree(n) {
  // 3^19 = 1162261467 is the max power of three in 32-bit signed int
  return n > 0 && 1162261467 % n === 0;
}

// n=27: 1162261467 % 27 = 0 → True  (3^3)
// n=9:  1162261467 % 9  = 0 → True  (3^2)
// n=6:  1162261467 % 6  = 3 → False (not power of three)
// n=12: 1162261467 % 12 = 3 → False (not power of three)

🔍 Why 3^19?

In a 32-bit signed integer system (Java's int), the maximum value is 2,147,483,647. The largest power of three below this is 3¹⁹ = 1,162,261,467. Every power of three divides this number because:

// If n = 3^k, then:
// 3^19 / n = 3^19 / 3^k = 3^(19-k) ∈ integer
// → No remainder → 3^19 % n == 0

// If n is NOT a power of three, the modulo is non-zero.
// The only divisors of 3^19 are powers of three!

Alternative: Iterative Division

function isPowerOfThree(n) {
  if (n <= 0) return false;
  while (n % 3 === 0) n /= 3;
  return n === 1;
}

// Time: O(log_3 n) — about 20 iterations max for 32-bit
// Space: O(1)

This is O(log n) vs the O(1) mathematical approach, but it works universally without needing to precompute the maximum power.

Key Insight

🔑 Key Insight: The 3^19 % n trick is O(1) but only works for 32-bit integers. For 64-bit, use 3⁴⁰ = 12,157,665,459,056,928,801. For Python's arbitrary-precision integers, pick the right maximum. The iterative approach is slower but works for ANY size.

Warning

⚠️ Interview Note: If the interviewer asks "What about powers of five? Powers of seven?" — the mathematical approach generalizes! Find the largest power of that base in the integer range, then check divisibility. But the iterative division approach always works.

PROBLEMPower of Three

Given an integer n, return true if it is a power of three. Use the mathematical approach: 3^19 = 1162261467 % n == 0.

Loading playground...

4. Integer Replacement — The Greedy Strategy

Problem: Given a positive integer n, you can apply these operations:

If n is even: replace n with n/2
If n is odd: replace n with either n+1 or n-1

Return the minimum number of operations to reduce n to 1. This is LeetCode 397, and it's a fascinating problem because the decision for odd numbers isn't obvious!

🤔 The Decision: Add or Subtract?

When n is odd, I face a choice: "Do I choose n+1 or n-1?" Both lead to an even number in the next step. This is the classic choose/not-choose dilemma. If I choose n-1, the next step gives (n-1)/2. If I choose n+1, the next step gives (n+1)/2. Which path leads to more consecutive divisions by 2? The answer depends on the binary pattern. If n ends with ...01, n-1 ends with ...00 (two trailing zeros). If n ends with ...11, n+1 ends with ...000 (at least three trailing zeros). More trailing zeros = more free divisions = fewer total steps!

🤔 The Dilemma

If n is even, the choice is obvious — divide by 2. That's always optimal.

But if n is odd? Both n+1 and n-1 are even, so both lead to a division by 2 in the next step. Which one leads to MORE consecutive divisions? That's the key to minimizing steps!

📋 Edge Cases to Consider

n = 1: Already at target. 0 steps. The while loop doesn't execute.
n = 2: 2 → 1. One division. 1 step.
n = 3: Special case! 3 → 2 → 1 (2 steps) is better than 3 → 4 → 2 → 1 (3 steps). The rule says subtract, not add.
n = Integer.MAX_VALUE (large odd): Adding 1 could overflow. In JavaScript, use >>> 0 or handle with BigInt.
n is very large (near 2^31): n+1 might overflow to a negative number in 32-bit signed. The division still works but may produce unexpected results.

✨ The Greedy Strategy

function integerReplacement(n) {
  let steps = 0;
  while (n !== 1) {
    if (n % 2 === 0) {
      n /= 2;           // Even: always divide by 2
    } else if (n === 3 || n % 4 === 1) {
      n -= 1;           // Odd, ends with 01: subtract
    } else {
      n += 1;           // Odd, ends with 11: add
    }
    steps++;
  }
  return steps;
}

// n=8  → 4 → 2 → 1: 3 steps (all even, clean)
// n=7  → 8 → 4 → 2 → 1: 4 steps (n%4=3 → add)
// n=5  → 4 → 2 → 1: 3 steps (n%4=1 → subtract)
// n=15 → 16 → 8 → 4 → 2 → 1: 5 steps (n%4=3 → add)
// n=3  → 2 → 1: 2 steps (special case: n-1 wins)

📊 Why The Greedy Choice Works

When n is odd, both n+1 and n-1 are even. The next step will be a division by 2. But the number we get after division determines how many MORE consecutive divisions we can perform:

n % 4	Binary Pattern	Choose	Why
1	...01	n - 1	n-1 ends in 00 → two divisions: (n-1)/2 is even
3	...11	n + 1	n+1 ends in 00 → at least two divisions: (n+1)/2 is even
n == 3	11	n - 1	Special case: 3→2→1 (2 steps) beats 3→4→2→1 (3 steps)

Key Insight

🔑 The Core Intuition: We want to maximize trailing zeros after each operation because trailing zeros mean free divisions by 2. Binary ...01 → subtract gives ...00 (two trailing zeros). Binary ...11 → add gives ...000 (three trailing zeros). The n=3 exception is because both paths converge at 2.

PROBLEMInteger Replacement

Given a positive integer n, replace it with n/2 if even, or n+1/n-1 if odd. Return the minimum steps to reduce n to 1. Use greedy strategy based on n mod 4.

Loading playground...

5. Binary String Reduction — Steps to Zero

Problem: Given a non-negative integer num, count the steps to reduce it to zero. In each step:

If the current number is even: divide by 2
If the current number is odd: subtract 1

This is LeetCode 1342, and it has a BEAUTIFUL closed-form solution once you understand the binary pattern.

🔍 Real-Time Thinking — What Do I Know?

"If n is even, divide by 2. If n is odd, subtract 1. Let me think about this in binary... Every time I divide by 2, I right-shift the binary representation by 1. Every time I subtract 1 from an odd number, I clear the LSB (turn the trailing 1 into 0). So each bit (except the MSB) needs one divide-by-2 operation. Each 1-bit needs one subtract-1 operation. That means total steps = (number of bits - 1) + (number of 1-bits). Let me verify with n=14 (1110): bits=4, ones=3. Steps = 4-1+3 = 6. That matches the step-by-step walkthrough!"

🤔 The Binary Insight

Let's read the binary representation from LEFT to RIGHT (MSB to LSB):

Every 1 bit needs: subtract 1 (to clear it) + divide by 2 (shift right)
Every 0 bit needs: divide by 2 only
The MSB (leftmost 1) only needs one subtract — no divide after the last bit

Formula: steps = (number of bits) - 1 + (number of 1 bits)

function numberOfSteps(num) {
  const binary = num.toString(2);   // "1110" for 14
  return binary.length - 1 + binary.split('1').length - 1;
  // Or simply: return binary.length - 1 + binary.replace(/0/g, '').length;
}

// Formula: steps = len(binary) - 1 + countOfOnes

// n=14: binary="1110", len=4, ones=3 → steps = 4-1+3 = 6
// n=8:  binary="1000", len=4, ones=1 → steps = 4-1+1 = 4
// n=0:  binary="0",    len=1, ones=0 → steps = 1-1+0 = 0

📊 Step-by-Step Walkthrough: n = 14

n	Binary	Operation	Steps Taken
14	1110	even → ÷2	1
7	0111	odd → -1	2
6	0110	even → ÷2	3
3	0011	odd → -1	4
2	0010	even → ÷2	5
1	0001	odd → -1	6
0	0000	done!	6 total

Key Insight

🔑 Why the Formula Works: Each bit position (except the MSB) requires a divide by 2 operation — that's len(binary) - 1divisions. Each 1 bit requires a subtract-1 operation — that's countOfOnes subtractions. Total = divisions + subtractions. The MSB's subtract is already counted in countOfOnes, and its "divide" doesn't exist because there's nothing to the left.

Edge Cases

n = 0: Already zero, 0 steps. Formula: "0" has len=1, ones=0 → 1-1+0 = 0 ✓
n = 1 (power of two): Binary "1", len=1, ones=1 → 1-1+1 = 1 step (just subtract 1)
n = 2 (power of two): Binary "10", len=2, ones=1 → 2-1+1 = 2 steps (÷2, -1)
n = 2ᵏ (any power of two): Binary "1" + k zeros, ones=1, len=k+1 → steps = k+1-1+1 = k+1

PROBLEMNumber of Steps to Reduce a Number to Zero

Given an integer num, return the number of steps to reduce it to zero. If even, divide by 2; if odd, subtract 1. Use the formula: steps = len(binary) - 1 + count('1').

Loading playground...

6. Gray Code — The Single-Bit Flip Sequence

Problem: An n-bit Gray code sequence is a sequence of 2ⁿ integers where every two consecutive integers differ by exactly one bit. Given n, return any valid n-bit Gray code sequence.

Gray code was invented by Frank Gray at Bell Labs in 1953 for pulse code communication. It's used in error correction, Karnaugh maps, rotary encoders, and ADC/DAC converters. And the formula is SURPRISINGLY simple.

Note

🎰 Real-World Analogy: Imagine a combination lock where each digit is a binary digit. Normal binary counting is like turning multiple dials at once (like a car odometer going from 0111 to 1000 — all four digits change). Gray code is like having a lock where you only turn ONE dial at a time. It's easier to read reliably because you never have a moment where multiple digits are changing simultaneously. The formula G(i) = i ^ (i >> 1) generates this sequence magically.

✨ The Magic Formula: G(i) = i ^ (i >> 1)

That's it. ONE XOR operation. For i from 0 to 2ⁿ-1, compute:

function grayCode(n) {
  const result = [];
  for (let i = 0; i < (1 << n); i++) {
    result.push(i ^ (i >> 1));  // The MAGIC formula
  }
  return result;
}

// n=3 (3 bits → 8 values):
// i=0 (000): G(0) = 0 ^ 0 = 0  = 000
// i=1 (001): G(1) = 1 ^ 0 = 1  = 001
// i=2 (010): G(2) = 2 ^ 1 = 3  = 011
// i=3 (011): G(3) = 3 ^ 1 = 2  = 010
// i=4 (100): G(4) = 4 ^ 2 = 6  = 110
// i=5 (101): G(5) = 5 ^ 2 = 7  = 111
// i=6 (110): G(6) = 6 ^ 3 = 5  = 101
// i=7 (111): G(7) = 7 ^ 3 = 4  = 100
// Sequence: [0, 1, 3, 2, 6, 7, 5, 4]

🔍 Why i ^ (i >> 1) Works

The formula maps each binary number i to a Gray code where consecutive values differ by exactly one bit. Here's the intuition:

i >> 1 shifts i right by one — this creates a "reference" pattern
XOR with the original produces a 1 wherever adjacent bits in i differ
As i increments by 1, exactly one bit in the Gray code toggles — this is the BEAUTY of Gray code!

Properties of Gray Code

Property	Description
Adjacent difference	Consecutive Gray codes differ by exactly 1 bit
Cyclic	First and last values also differ by 1 bit (length is power of two)
Unique	Each value appears exactly once in the sequence
Binary → Gray	G = i ^ (i >> 1)
Gray → Binary	i = G; while (G >>= 1) i ^= G

Gray Code to Binary Conversion

function grayToBinary(gray) {
  let binary = gray;
  while (gray >>= 1) {
    binary ^= gray;   // XOR all shifted versions
  }
  return binary;
}

// Example: gray=5 (101) → binary?
// Iteration 1: gray >>= 1 → gray=2 (10), binary = 5 ^ 2 = 7 (111)
// Iteration 2: gray >>= 1 → gray=1 (1),  binary = 7 ^ 1 = 6 (110)
// Iteration 3: gray >>= 1 → gray=0, stop
// Result: 6 (110) — indeed, binary 6 → Gray = 6 ^ 3 = 5 ✓

Tip

⚡ Pro Tip: The Gray Code sequence length is ALWAYS a power of two (2ⁿ). The sequence wraps around cyclically — the last value differs from the first by exactly one bit. This is why Gray code is so useful in rotary encoders: even if the encoder is in a "transitional" position, you never get garbage readings.

PROBLEMGray Code

An n-bit Gray code sequence is a sequence of 2^n integers where consecutive integers differ by exactly one bit. Generate the sequence using: gray = i ^ (i >> 1).

Loading playground...

🎯 Interview Cheat Sheet

Key Insight

Q1: What's the O(1) trick to check power of two?
n > 0 && (n & (n-1)) === 0. The AND clears the lowest set bit. If the result is 0, there was only one set bit — that's a power of two.

Key Insight

Q2: How does power of four differ from power of two?
Every power of four is a power of two, but the reverse isn't true. Add the check (n & 0x55555555) !== 0 to ensure the lone bit is at an even position. Or use (n-1) % 3 === 0.

Key Insight

Q3: Why can't we use bit tricks for power of three?
Because 3 is not a power of two. Powers of three have no consistent binary pattern. Use the mathematical approach: largest power of three in 32-bit ÷ n has no remainder. Or use iterative division.

Key Insight

Q4: What's the greedy rule for Integer Replacement?
Even → divide. Odd and n%4==1 (or n==3) → subtract. Odd and n%4==3 → add. This maximizes trailing zeros after the next operation, giving more free divisions.

Key Insight

Q5: What's the formula for steps to reduce a number to zero?
steps = len(binary) - 1 + count_of_1_bits. Each bit (except MSB) needs a divide. Each 1-bit needs a subtract. That's the whole formula.

Key Insight

Q6: How do you generate Gray Code?
G(i) = i ^ (i >> 1) for i from 0 to 2ⁿ-1. Each consecutive pair differs by exactly one bit. To convert back: XOR with all right-shifted versions of the Gray code.

Key Insight

Q7: How does n & (-n) isolate the lowest set bit?
In two's complement, -n = ~n + 1. When you AND n with -n, only the lowest set bit survives. For a power of two, n & (-n) === n.

📝 Key Takeaways

Power of two — n > 0 && (n & (n-1)) === 0. Exactly one set bit = power of two. This is THE most important bit trick.
Power of four — Power of two + even-position mask (n & 0x55555555). The lone bit must be at an even position.
Power of three — Cannot use bit tricks. Use math:3^19 % n === 0 (32-bit) or iterative division.
Integer Replacement — Greedy strategy: even → ÷2, odd→n%4==1 → -1, odd→n%4==3 → +1. Maximize trailing zeros for free divisions.
Binary String Reduction — Formula:steps = len(binary) - 1 + count('1'). Every bit tells you what to do.
Gray Code — G(i) = i ^ (i >> 1). Generates a sequence where consecutive values differ by exactly one bit.
Different bases need different approaches — Power-of-two bases (2, 4, 8, 16) use bit ops. Non-power-of-two bases (3, 5, 7) use math.
Time: O(1), Space: O(1) — Bit manipulation solutions are always constant time and space. Mathematical approaches are also O(1) for fixed-width integers.
Understand WHY — Don't just memorize formulas. Understand the binary patterns: why n&(n-1) clears the lowest set bit, why trailing zeros mean free divisions, why XOR with shift produces Gray code.
Practice! — The only way this becomes second nature is by solving problems. The Playground is your dojo 🥋

Note

🔮 What's Next? Now that you've mastered power detection, head over to Bit Masking & Complementsto learn about complement, binary gap, base conversion, and more!