Bit manipulation

The operators, and what they actually do

Trick 1 — XOR cancels itself out

x ^ x === 0 and x ^ 0 === x, for any x. XOR-ing a whole list together makes every value that appears an even number of times vanish, leaving only what's left over.

// find the single number that doesn't appear exactly twice — O(n) time, O(1) space
function singleNumber(nums) {
  let result = 0;
  for (const num of nums) result ^= num; // every pair cancels to 0
  return result; // whatever's left is the unpaired one
}

This is a genuinely elegant O(1)-space answer to a problem that looks like it needs a hash set (O(n) space) — worth recognizing "appears an even number of times except one" as an XOR tell.

Trick 2 — check, set, and clear a specific bit

function getBit(num, i)   { return (num >> i) & 1; }        // is bit i a 1?
function setBit(num, i)   { return num | (1 << i); }         // force bit i to 1
function clearBit(num, i) { return num & ~(1 << i); }         // force bit i to 0
function toggleBit(num, i){ return num ^ (1 << i); }          // flip bit i

1 << i builds a number that's all zeros except a single 1 at position i — every one of these four operations is just combining that "mask" with the original number using the right bitwise operator.

Trick 3 — the lowest set bit, and counting set bits

// n & (n - 1) clears the LOWEST set bit — used constantly
function countSetBits(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // each iteration removes exactly one 1-bit
    count++;
  }
  return count; // loop runs once per set bit, not once per bit position — faster than checking all 32
}

// is n a power of 2? a power of 2 has EXACTLY one set bit
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

Trick 4 — bitmasks as a compact set

For a small, fixed universe of items (say, ≤ 20-30 elements), an integer can represent an entire subset — bit i set means "item i is in the set." This is the foundation of bitmask DP (advanced tier): a whole subset becomes a single number you can use as a state or a Map key, instead of an array you'd need to compare element-by-element.

let mask = 0;
mask |= (1 << 3);        // add item 3 to the set
const has3 = (mask & (1 << 3)) !== 0; // is item 3 in the set?
mask &= ~(1 << 3);        // remove item 3

Recognizing it in an unseen problem

• "Without using extra space," combined with numbers that appear in pairs → XOR
• "Count sallow bits," "power of two," "single bit differs" → the set-bit tricks above
• A small fixed number of items/states (≤ ~20) where you need to represent "which subset" compactly → bitmask
• Multiplying/dividing by exact powers of 2 in a performance-sensitive inner loop → shifts, though modern engines often optimize this automatically