Bit Manipulation Pattern

When to use Bit Manipulation

• Every element appears twice (or k times) except one — XOR across the array isolates the outlier in a single pass with no hash map.
• You need to count set bits, check parity, or determine whether a number is a power of two using a constant-time bit trick.
• The problem operates on subsets of a small (n <= 20) universe and you can encode each subset as an integer bitmask.
• You need to swap, set, clear, or toggle a specific bit by index without touching the rest of the integer.
• Arithmetic operators are forbidden by the problem (Sum of Two Integers) and you must simulate addition with XOR + carry shifts.

Template

function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

function countSetBits(x) {
  let count = 0;
  while (x !== 0) {
    x &= (x - 1);
    count++;
  }
  return count;
}

function setBit(x, i) { return x | (1 << i); }
function clearBit(x, i) { return x & ~(1 << i); }
function checkBit(x, i) { return (x >> i) & 1; }

Common mistakes

• Forgetting that JavaScript bitwise operators coerce to 32-bit signed integers, which silently overflows on values above 2^31 and breaks problems like Reverse Bits that expect 32 unsigned bits.
• Writing `x & 1 == 0` instead of `(x & 1) === 0` — comparison binds tighter than bitwise AND in most languages, producing nonsense results.
• Using `x % 2` for parity inside a tight loop and missing the faster `x & 1` trick that interviewers often want to see.
• On Single Number II (every element three times except one), trying to apply XOR directly — XOR only cancels pairs, so the three-times variant needs a two-state counter or a bit-by-bit modular count.
• Confusing logical right shift (`>>>` in JS) with arithmetic right shift (`>>`), which sign-extends and corrupts the high bits of a negative integer.