Bit Manipulation Pattern

Why this pattern matters for LeetCode

XOR is the most useful bitwise trick in LeetCode: a ^ a = 0 (a number XORed with itself cancels) and a ^ 0 = a (XORing with 0 leaves the number unchanged). XOR every number in an array of pairs plus one unique number, all pairs cancel, leaving just the unique number. No hash map, no sorting, O(1) space. This pattern appears in Single Number, Missing Number, and similar problems. It's also the foundation for checking individual bits, counting set bits, and testing powers of two.

What the Bit Manipulation pattern is

Bit manipulation treats integers as sequences of binary digits and uses bitwise operators to inspect or modify individual bits. XOR (^) is the workhorse: it returns 1 when bits differ and 0 when they match, so identical values cancel completely. AND (&) isolates specific bits: n & 1 checks the last bit (0 if even, 1 if odd). Shifts multiply (<<) or divide (>>) by powers of two. The canonical tricks: XOR everything to find the lone survivor among pairs; use n & (n-1) to clear the lowest set bit; check n & (n-1) === 0 to test for a power of two.

Reach for Bit Manipulation when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Bit Manipulation

• ✓Single Number. XOR all elements; pairs cancel to 0, unique number survives
• ✓Missing Number. XOR all indices 0 to n with all array values; the missing index survives
• ✓Number of 1 Bits, use n & (n - 1) to clear the lowest set bit; count iterations until n is 0
• ✓Power of Two, n & (n - 1) === 0 means exactly one bit is set, which is a power of two
• ✓Counting Bits. DP with bit shift: bits[n] = bits[n >> 1] + (n & 1)

When NOT to use Bit Manipulation

• ✕The problem doesn't involve individual bit manipulation, most array and string problems don't
• ✕You need to store arbitrary key-value data, a hash map is the right tool
• ✕The input is a string or floating-point number, bit manipulation targets integer bit patterns
• ✕You're forcing a bitwise solution when a hash map would be cleaner, don't reach for bit tricks just to be clever

Better alternative: In those cases, a hash map (for key-value lookups), a Set (for existence checks), or sorting (for ordered access) is clearer and more appropriate.

JavaScript code template

Single Number, Power of Two, and Hamming Weight. O(n) or O(1) time, O(1) space

// Single Number. XOR cancels duplicate pairs
function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

// Power of Two, exactly one bit is set
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
  // n - 1 flips all bits below the single 1 bit
  // n & (n - 1) clears it, result is 0 only for powers of two
}

// Number of 1 Bits, clear lowest set bit each iteration
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // strips the lowest 1 bit
    count++;
  }
  return count;
}

XOR: a ^ a = 0 and a ^ 0 = a. XOR-ing every element means pairs cancel to 0 and the unique element XORs with 0, surviving unchanged. For Power of Two: any power of two in binary is a single 1 bit. Subtracting 1 flips all lower bits and turns the 1 to 0. AND-ing n with n-1 clears the only set bit, result is 0 if and only if n was a power of two. For Hamming Weight: n & (n-1) removes the lowest set bit each step; count how many steps until n is 0.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Identify what bitwise property the problem exploits: XOR cancellation, bit counting, power-of-two check, or shifts.
2. 2For XOR problems: initialize result = 0, XOR every element. Pairs disappear; the unique value remains.
3. 3For bit counting: use n & (n - 1) to strip the lowest set bit in each iteration until n is 0.
4. 4For power-of-two: check n > 0 && (n & (n - 1)) === 0.
5. 5For even/odd: check n & 1. 0 is even, 1 is odd.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Single Number

  XOR all elements. Every pair cancels to 0, leaving the unique value.

  Coming soon
• Number of 1 Bits

  Use n & (n - 1) to clear the lowest set bit each iteration. Count steps until n is 0.

  Coming soon
• Counting Bits

  DP with bit shift: bits[n] = bits[n >> 1] + (n & 1). Builds answers for 0 to n in one pass.

  Coming soon
• Missing Number

  XOR indices 0..n with all array values. The missing index is the only one that doesn't get cancelled.

  Coming soon
• Reverse Bits

  Extract the last bit of n, shift it into the result position, shift n right. Repeat 32 times.

  Coming soon

Common mistakes beginners make

• ✕XOR-ing when elements appear three times instead of two. XOR cancels pairs, not triples. Single Number II (three duplicates) requires counting set bits across all numbers, not XOR.
• ✕Forgetting that n & (n - 1) clears the lowest set bit, not the highest, don't confuse it with other masking operations.
• ✕Using == instead of === when comparing bitwise results in JavaScript, bitwise operators return integers and unexpected type coercion can produce wrong comparisons.
• ✕Applying bit manipulation when a hash map is more readable, bit tricks are not always the right tool. Only use them when the space optimization matters or the pattern is genuinely cleaner.

Bit Manipulation vs Hash Map vs Sorting

Choose the right tool for the job.

Time and space complexity

XOR-based solutions loop through the input once. O(n). Single-operation checks (power of two, even/odd) run in O(1). Bit count with n & (n-1) runs in O(k) where k is the number of set bits, at most O(log n). No extra data structures are needed, just integer variables, so space is always O(1).

Frequently asked questions

Why does XOR work for finding the unique number?

XOR has two properties: a ^ a = 0 (same values cancel) and a ^ 0 = a (XOR with 0 is identity). XOR-ing every element means all pairs cancel to 0. The one unpaired element XORs with the accumulated 0 and survives unchanged. Order doesn't matter. XOR is commutative and associative.

What does n & (n - 1) actually do?

It clears the lowest set bit in n. Here's why: n has some lowest 1 bit at position k. n - 1 flips that bit to 0 and sets all lower bits to 1. AND-ing n with n - 1 clears position k (n-1 has 0 there) and keeps all higher bits (n-1 has the same values there as n). The result is n with its lowest 1 bit removed.

When should I use bit manipulation vs a hash set?

Use bit manipulation when the problem specifically exploits binary properties, pair cancellation, bit counting, power-of-two checks. Use a hash set when you need to track which elements have been seen and retrieve data about them. Don't force bitwise tricks on a problem that's cleaner with a hash set.

Which bit operators do I actually need to know for LeetCode?

Mainly five: ^ (XOR, pair cancellation), & (AND, bit checking and clearing), | (OR, bit setting), << (left shift, multiply by 2^k), >> (right shift, divide by 2^k). The XOR pattern and n & (n-1) trick cover the vast majority of bit manipulation problems.