Bit manipulation

The operators, and what they actually do

Two's complement: how negative numbers look in 32 bits

Every tip below that touches a negative number depends on one fact, so it is worth deriving once. A 32-bit pattern is just 32 digits of 0 or 1, and adding 1 to the largest pattern (all ones) wraps around to all zeros, the same way an odometer rolls over. That wrap-around gives a natural meaning to "minus": the pattern that, added to x, wraps to zero is -x. Flipping every bit of x gives a pattern that adds to x to make all ones, so adding one more finishes the wrap: -x === ~x + 1, and the same line read backwards says ~x === -x - 1. This encoding is called two's complement. The top bit acts as the sign (it counts as −2³¹), so the representable range is −2³¹ to 2³¹ − 1 with no special case for negatives.

JavaScript does the same with 32 bits instead of 4. Negating 6 in 8 bits to keep the digits short: 6 is 00000110, ~6 is 11111001, adding 1 gives 11111010, and that pattern is -6. Note that the range is lopsided: there is one more negative value than positive, so there is no +2³¹: negating -2147483648 as a plain number gives 2147483648, but squeezed back into 32 bits (-(-2147483648) | 0) it lands on -2147483648 again.

Reading the shifts on negative numbers

To look at a number's bits, print it unsigned. (-6).toString(2) gives "-110", which is the mathematical sign followed by the magnitude and hides the real pattern, while (-6 >>> 0).toString(2) gives the 32 actual bits, 11111111111111111111111111111010. Pad with .padStart(32, "0") when the number is small.

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
}

Dry run: singleNumber([4, 1, 2, 1, 2])

Every value that appears twice (1 and 2) XORs itself away over the course of the loop — the last two rows undo exactly what rows 2 and 3 did. Only 4, the unpaired value, survives to the end.

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.

Missing Number: XOR the indices in too

An array holds n distinct values from 0..n, so exactly one value is missing. The shape "everything cancels except one" is there if you supply the second copy yourself: XOR together every index 0..n and every value in the array. Each value that is present appears twice (once as an index, once as a value) and cancels; the missing value appears only as an index, so it is what remains. The alternative n * (n + 1) / 2 - sum is also O(n) time and O(1) space, and it is fine for sizes an interview uses; XOR never leaves 32 bits, which is its advantage when the sum would be huge.

function missingNumber(nums) {
  let x = nums.length; // start with n, the one index the loop below does not visit
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
  return x;
}

Dry run: missingNumber([3, 0, 1])

The indices 0, 1, 2 and the extra 3 meet the values 3, 0, 1 and cancel pair by pair; 2 has an index but no value, so it survives. Seeding x with n is easy to forget: the loop visits only the indices 0..n-1, so without the seed the value n is left uncancelled and the function returns missing ^ n instead of missing.

Single Number II: when pairs become triples

Now every value appears three times except one that appears once. XOR no longer helps, because x ^ x ^ x is x, not 0. Change the unit of thinking from numbers to bit columns. Look at one bit position across the whole array: every value that appears three times contributes 0 or 3 ones to that column, so the column total is a multiple of 3 plus the lone value's bit. The total modulo 3 is therefore exactly the lone value's bit.

function singleNumberII(nums) {
  let result = 0;
  for (let bit = 0; bit < 32; bit++) { // all 32 columns, including the sign bit
    let ones = 0;
    for (const num of nums) ones += (num >> bit) & 1;
    if (ones % 3 !== 0) result |= 1 << bit;
  }
  return result; // bit 31 set makes this come out negative, which is correct
}

Bits 1 and 0 are both set, so the answer is 11 in binary, which is 3. This costs O(32 n) = O(n) time and O(1) space. Stopping the loop at bit 30 instead of 31 is the usual bug: it works for every non-negative input and silently returns the wrong value when the lone number is negative.

The same idea can run in a single pass without a 32-step outer loop. Give every bit column a two-bit counter that counts 0, 1, 2 and then back to 0, stored across two variables: ones holds the low bit of every column's counter and twos the high bit, so the pair (twos, ones) cycles 00, 01, 10, 00 for a column that keeps seeing a 1.

function singleNumberIIFast(nums) {
  let ones = 0, twos = 0;
  for (const num of nums) {
    ones = (ones ^ num) & ~twos; // toggle the low bit, unless the counter was at 2 (it wraps to 0)
    twos = (twos ^ num) & ~ones; // toggle the high bit, unless the low bit just became 1
  }
  return ones; // columns of the lone value are at count 1; every tripled column is back at 0
}

Dry run on [2, 2, 3, 2], showing the low four bits

Both versions are O(n). The column-counting version generalises at once to "every value appears k times except one" by changing 3 to k; the two-variable version needs a bigger counter for each extra value of k, so say the first one in an interview and keep the second as the follow-up.

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;
}

Isolating the lowest set bit with negation

n & (n - 1) removes the lowest set bit. Its twin keeps only that bit: n & -n. The two's complement identity explains it. Write n as some high part, then its lowest 1, then zeros. Flipping gives the inverted high part, a 0, then ones; adding 1 carries through those ones, turns them back into zeros and sets the 0 to 1. So -n is the inverted high part followed by the same lowest 1 and the same zeros. ANDing with n cancels the high part (a bit and its opposite) and keeps the lowest 1.

The result is a power of two, the weight of the lowest set bit. It is 0 for n = 0, and it stays correct for -2147483648, where it returns the sign bit -2147483648 itself. The same expression drives Fenwick trees later, where it steps between the ranges a node covers.

Single Number III: two survivors, separated by one bit

Every value appears twice except two values, a and b, which appear once. XOR-ing the whole array gives a ^ b, which is not enough on its own. But a !== b, so a ^ b has at least one 1-bit, and at that position a and b differ. Split the array by that bit. Both copies of any paired value land in the same half (they have the same bits), so each half is the "all pairs, one survivor" problem, and Trick 1 solves each half. xor & -xor picks the splitting bit in one step.

function singleNumberIII(nums) {
  let xor = 0;
  for (const num of nums) xor ^= num; // xor === a ^ b
  const bit = xor & -xor;              // one position where a and b differ

  let a = 0, b = 0;
  for (const num of nums) {
    if (num & bit) a ^= num; else b ^= num; // pairs cancel inside their own half
  }
  return [a, b];
}

Dry run: singleNumberIII([1, 2, 1, 3, 2, 5])

Two passes, O(n) time and O(1) space. The answer comes back in an unspecified order, so compare the two values as a set. If you reached for xor & 1 as the splitting bit it breaks as soon as a and b agree at bit 0; the lowest set bit of the XOR is the one guaranteed to separate them.

Counting bits for every number up to n

Calling countSetBits on each of 0..n costs O(n log n) in the worst case. The answers for neighbouring numbers are related, though. Dropping the last bit of i gives i >> 1, a smaller number whose answer is already in the table, and the dropped bit is i & 1: bits[i] = bits[i >> 1] + (i & 1). A table built in increasing order is a small dynamic program with O(1) work per entry.

function countBits(n) {
  const bits = new Array(n + 1).fill(0); // bits[0] = 0 is the base case
  for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
  return bits;
}

Dry run: countBits(8)

O(n) time and O(n) space for the table itself. An equivalent recurrence, bits[i] = bits[i & (i - 1)] + 1, reuses the lowest-set-bit removal from Trick 3 instead of the shift: i & (i - 1) is always smaller than i and has one fewer set bit.

Hamming distance: how many bits differ

The Hamming distance between two integers is the number of bit positions where they differ. XOR is 1 exactly where two bits differ, so the distance is the count of set bits in a ^ b: reuse countSetBits and write countSetBits(a ^ b). For a whole array, comparing every pair is O(n²) pairs, but the bit columns come to the rescue again. If a column holds ones ones and n - ones zeros, exactly ones * (n - ones) pairs differ in it, and the columns are independent, so the total over all pairs is the sum over 32 columns.

function totalHammingDistance(nums) {
  let total = 0;
  for (let bit = 0; bit < 32; bit++) {
    let ones = 0;
    for (const num of nums) ones += (num >> bit) & 1;
    total += ones * (nums.length - ones); // pairs with one 1 and one 0 in this column
  }
  return total;
}

O(32 n) time against O(n²) for the pair loop, and O(1) space. countSetBits from Trick 3 also terminates on negative inputs (it clears one set bit per step until the value is 0), so a negative argument is counted by its 32-bit pattern, not as a magnitude.

Reversing the 32 bits of a number

Read the number from its lowest bit upward and build the answer from the highest bit downward: shift the result left to make room, copy the lowest bit of the input in, and shift the input right so the next bit becomes the lowest.

function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1); // make room, then append the lowest bit of n
    n >>>= 1;                          // logical shift: do not drag a sign bit in from the left
  }
  return result >>> 0; // the final pattern may have bit 31 set; read it back as unsigned
}

Two JavaScript details decide whether this passes. Using >> instead of >>> for the input would copy the sign bit into the empty positions for a negative n, though with exactly 32 iterations the loop reads only the original 32 bits either way; using >>> is the habit that does not depend on that counting argument. And the result must end in >>> 0: when the original number was odd, the reversed one has bit 31 set, and without the conversion the function returns a negative number where the unsigned value was expected. For 43261596 the answer is 964176192.

When the function is called millions of times, the loop's 32 steps can be replaced by five fixed ones that swap halves, then bytes, then nibbles, then pairs, then single bits:

function reverseBitsFast(n) {
  n = ((n >>> 16) | (n << 16)) >>> 0;
  n = (((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8)) >>> 0;
  n = (((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)) >>> 0;
  n = (((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2)) >>> 0;
  n = (((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)) >>> 0;
  return n;
}

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

Enumerating every subset, and every submask of a mask

If the mask is a set, counting from 0 up to 2ⁿ - 1 visits every possible set once, because each number in that range is a different pattern of n bits. Bit i of the counter says whether item i is chosen. This is the compact iterative form of "include or skip each item".

function allSubsets(items) {
  const n = items.length;
  const result = [];
  for (let mask = 0; mask < 2 ** n; mask++) { // 2 ** n, not 1 << n, so n = 31 and n = 32 do not break
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(items[i]);
    }
    result.push(subset);
  }
  return result;
}

The cost is O(n · 2ⁿ): 2ⁿ masks, each scanned bit by bit. The loop bound matters. 1 << 31 is negative and 1 << 32 is 1, so a bound written as 1 << n runs zero or one times for n of 31 or 32. A subset enumeration that large is hopeless anyway, so in practice the constraint is n of about 20 or less, but write the bound so that the code is right for the whole range it can be asked about.

A harder variant needs only the submasks of a given mask: every subset of the items already in mask. The elegant loop below visits them from largest to smallest without ever looking at an item outside the mask.

function submasks(mask) {
  const out = [];
  for (let sub = mask; ; sub = (sub - 1) & mask) {
    out.push(sub);
    if (sub === 0) break; // 0 is the last submask; without this stop the loop would never end
  }
  return out;
}

Why does (sub - 1) & mask step to the next smaller submask? Subtracting 1 turns the lowest set bit of sub into 0 and every zero below it into 1. ANDing with mask then removes the bits that are not allowed, so the result is the largest value that is smaller than sub and still made only of mask bits. No submask is skipped because any pattern between them would have to be larger than the result and smaller than sub.

Dry run: submasks(0b1011)

A mask with k set bits has 2^k submasks. If a bitmask DP loops over every mask and then over all its submasks, the total work is 3ⁿ, because each item is in one of three states: outside the mask, in the mask but not in the submask, or in both. That is far less than the 4ⁿ of two nested loops over all masks, and it is the complexity to quote for partition-style DPs.

Gray code: change one bit at a time

A Gray code lists all n-bit patterns so that consecutive patterns differ in exactly one bit. The direct formula is i ^ (i >> 1).

function grayCode(n) {
  const out = [];
  for (let i = 0; i < 2 ** n; i++) out.push(i ^ (i >> 1));
  return out;
}

Why one bit changes: going from i to i + 1 flips the trailing ones of i and the zero above them, say the lowest k + 1 bits, so i ^ (i + 1) is 2^k+1 - 1. The shifted copy flips the lowest k bits, 2^k - 1. XOR-ing the two changes leaves 2^k, a single bit. The last code, 100, also differs from the first, 000, by one bit, so the list is a cycle. Gray codes are the ordering behind "visit every subset by adding or removing one item at a time".

Power of four: one set bit, at an even position

A power of four is a power of two whose single set bit sits at position 0, 2, 4 and so on, so first check that there is exactly one set bit and then check where it is. A mask with a 1 at every even position, 0x55555555, answers the second question in one AND.

function isPowerOfFour(n) {
  return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
}

// an equivalent last test: 4 ** k leaves remainder 1 when divided by 3, 2 * 4 ** k leaves 2
function isPowerOfFourMod(n) {
  return n > 0 && (n & (n - 1)) === 0 && n % 3 === 1;
}

Both tests run in O(1). The common mistakes are using the mask with the odd positions (0xAAAAAAAA, which accepts 2 and 8 and rejects 1 and 4) and forgetting n > 0: 0 and -2147483648 both pass the single-bit test ((0 & -1) === 0, and -2147483648 & 2147483647 is 0 too), so they must be rejected first.

Bitwise AND of a range: keep the common prefix

AND all integers from left to right, inclusive. A loop over the range is O(right - left), which is too slow when the range is billions wide. Look at the binary forms. Take the highest bit position where left and right differ. Above it they agree. At that position left has 0 and right has 1, so the range contains a number with the shared prefix followed by 1 and all zeros, and the number just before it, the shared prefix followed by 0 and all ones. The lower bits (that position and everything below) therefore take both values across the range, and ANDing them gives 0. The answer is the common prefix of the two endpoints, padded with zeros.

function rangeBitwiseAnd(left, right) {
  let shift = 0;
  while (left !== right) { // until only the shared prefix is left
    left >>= 1;
    right >>= 1;
    shift++;
  }
  return left << shift;  // put the prefix back in place, zeros below
}

// same answer, using Trick 3: strip the lowest set bit of right until right is not above left
function rangeBitwiseAnd2(left, right) {
  while (right > left) right &= right - 1;
  return right;
}

Dry run: rangeBitwiseAnd(5, 7), that is 101 and 111

Checking: 5 & 6 & 7 is 4. At most 31 shifts, so the first version is O(log right) and the second clears one bit per step, also O(log right). The second works because, while right is still above left, it keeps a 1 at the highest bit where the two differ, so clearing its lowest set bit never overshoots; the loop stops when that differing bit itself is cleared, leaving exactly the common prefix. Both assume 0 <= left <= right < 231, the usual constraint; the answer for (0, 2147483647) is 0.

Adding without plus: sum of two integers

Adding in binary has two parts per column: the sum bit and the carry. The sum bit ignoring carries is a ^ b (1 plus 1 is 0 here). The carry is generated where both bits are 1 and moves one column up: (a & b) << 1. So a + b equals (a ^ b) + ((a & b) << 1), which is the same problem with a carry that has moved one position left. Repeat until the carry is 0.

function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1; // columns where both are 1 produce a carry into the next column
    a = a ^ b;                 // the sum without those carries
    b = carry;                 // add the carries in the next round
  }
  return a;
}

Dry run: getSum(5, 3)

After round 4 the carry is 0 and a is 1000, which is 8. In JavaScript the loop ends for negative inputs too, because the carry is pushed up and finally off the 32-bit edge, so it needs at most 32 rounds. The result equals (a + b) | 0: the same 32-bit wrap-around a hardware adder gives, so getSum(2147483647, 1) is -2147483648. Worth saying out loud: this is a ripple-carry adder, with XOR as the sum bit and AND as the carry.

Dividing without the division operator

Long division in binary is repeated subtraction made fast by doubling. Subtracting the divisor one at a time costs as many steps as the quotient, up to 2³¹. Instead, find the largest divisor · 2s that still fits in what is left of the dividend, subtract it, add 2^s to the quotient, and go on with smaller s. Because every integer is a sum of distinct powers of two, trying s from 31 down to 0 builds the quotient exactly, in at most 32 steps.

function divide(dividend, divisor) {
  const INT_MAX = 2147483647;
  if (dividend === -2147483648 && divisor === -1) return INT_MAX; // the one result that does not fit in 32 bits

  const negative = (dividend < 0) !== (divisor < 0);
  let remaining = Math.abs(dividend); // absolute values up to 2 ** 31: safe in a double, not in an int32
  const step = Math.abs(divisor);
  let quotient = 0;

  for (let shift = 31; shift >= 0; shift--) {
    const chunk = step * 2 ** shift; // multiplying by a power of two is exact; step << shift would wrap
    if (chunk <= remaining) {
      remaining -= chunk;
      quotient += 2 ** shift;
    }
  }
  return negative ? 0 - quotient : quotient; // 0 - q, not -q: -0 would print as -0 when q is 0
}

Dry run: divide(43, 5)

43 divided by 5 truncates to 8. The sign handling mirrors JavaScript's own Math.trunc(a / b): the quotient truncates toward zero, so divide(7, -3) is -2 and divide(-7, 3) is -2 as well. Three details cost people the offer here: the -2147483648 / -1 overflow, working with the absolute value of -2147483648 (2147483648 does not exist as an int32, so keep it in an ordinary number), and the 32-bit << that silently wraps when the shifted divisor passes bit 31. The time is O(32), a constant.

Prefix XOR: range XOR in O(1), and counting subarrays

XOR undoes itself, which makes it behave like subtraction for ranges. Define prefix[i] as the XOR of the first i elements. Then prefix[r + 1] ^ prefix[l] is the XOR of nums[l..r]: the common first l elements appear in both prefixes and cancel. This is the prefix-sum idea with XOR in place of plus, and the subtraction step is XOR itself.

function buildPrefixXor(nums) {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] ^ nums[i];
  return prefix;
}

function xorRange(prefix, left, right) {
  return prefix[right + 1] ^ prefix[left]; // O(1) per query after O(n) setup
}

The counting form is the hash map trick from prefix sums. A subarray (i, j] has XOR k exactly when prefix[j] ^ prefix[i] === k, that is when prefix[i] === prefix[j] ^ k. Scan once, keep a map of how many times each prefix value has been seen, and at each step add the number of earlier prefixes equal to current ^ k.

function subarraysWithXor(nums, k) {
  const seen = new Map([[0, 1]]); // the empty prefix, so subarrays that start at index 0 count
  let prefix = 0, count = 0;
  for (const num of nums) {
    prefix ^= num;
    count += seen.get(prefix ^ k) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

Dry run: subarraysWithXor([4, 2, 2, 6, 4], 6)

The four subarrays are [4, 2], [6], [2, 2, 6] and the whole array, each with XOR 6; the algorithm costs O(n) time and O(n) space. A related puzzle, "count triples i < j <= k where the XOR of arr[i..j-1] equals the XOR of arr[j..k]", reduces to the same fact: the two halves are equal exactly when the XOR of the whole range arr[i..k] is 0, and then every split point j works, so each zero-XOR range contributes k - i triples. Checking all ranges is O(n²) with a running XOR, and a map of prefix values brings it to O(n).

Recognizing it in an unseen problem

• "Without using extra space," combined with numbers that appear in pairs → XOR
• "Count set bits," "power of two," "power of four," "single bit differs," "Hamming distance" → the set-bit tricks above
• Every value appears twice (or three times) except one or two → XOR, or per-column counting modulo the repeat count; for two survivors, split by the lowest set bit of the XOR
• "Without using +, -, * or /" → the carry loop for addition, shift-and-subtract for division
• A range of consecutive integers combined with AND → the common binary prefix of the two endpoints
• "Range XOR queries" or "count subarrays whose XOR is k" → prefix XOR, with a map of prefix counts for the counting version
• "Every subset," "every submask," "visit all states changing one item at a time" → count a mask from 0 to 2ⁿ - 1, the submask loop, or a Gray code
• Any negative input in a bit problem → ask what you want, the signed 32-bit value or the unsigned pattern, and convert with | 0 or >>> 0 at the boundary
• 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