Bit Manipulation

How It Works

Every integer is stored in memory as a fixed-width sequence of bits (32 bits for a JS bitwise operation, since JS coerces operands to 32-bit signed integers before applying bitwise operators). Bit manipulation means operating directly on that binary representation using operators like & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), and >> / >>> (right shift, signed/unsigned).

Each operator has a predictable, mechanical effect: AND-ing with a mask isolates specific bits, OR-ing sets bits, XOR-ing toggles bits (and famously cancels a value with itself: x ^ x === 0), and shifting multiplies or divides by powers of two extremely cheaply, since it's just moving bits left or right rather than doing arithmetic. Because these operations work on the raw representation rather than looping over digits or characters, they run in constant time and use no extra memory beyond the number itself, which is why bit tricks show up in performance-sensitive and space-constrained problems.

A common building block is using an integer as a bitmask: each bit represents a boolean flag or the presence/absence of an item in a small set. This lets you represent a whole subset of up to 32 items as a single number, and check, set, or clear membership in O(1).

When To Use It

Look for bit manipulation when a problem explicitly mentions powers of two, XOR, or asks you to solve something "without using extra space"; these are strong hints that a bitwise trick replaces what would otherwise require an auxiliary array or set.

It's also the classic tool for "find the single unique element among duplicates" problems: XOR-ing every element together cancels out anything that appears an even number of times, leaving only the odd-one-out, in O(n) time and O(1) space; something a hash set could also do, but not without extra memory.

When the input space is small enough to be represented as a bitmask (e.g. subsets of up to ~20-30 items, visited states in a graph, or flags in dynamic programming, known as bitmask DP), encoding state as an integer instead of an array or set is both faster and dramatically more memory-efficient.

Finally, if a problem talks directly about binary representations, counting set bits, or manipulating individual bits/flags, that's a direct signal rather than an inference; just use the bitwise operators.

Time & Space Complexity

Most individual bitwise operations (&, |, ^, <<, >>) are O(1); the hardware performs them on the whole word at once, not bit by bit. Operations that inspect or count every bit in a number (like counting set bits with a naive loop, or converting to a binary string) are O(log n) relative to the value of n, since a number n has roughly log2(n) bits.

Space complexity is the real draw: bit tricks typically need O(1) extra space, because the "data structure" is just the integer itself. This is what makes bitmask DP so powerful: representing a set of up to 30 elements as a single 32-bit integer instead of an array turns an otherwise memory-heavy state space into a single number you can use directly as a DP array index.

// Check if a number is a power of two.
// Powers of two have exactly one set bit (100, 1000, ...).
// n & (n - 1) clears the lowest set bit; if that leaves 0, only one bit was set.
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// Count set bits (Brian Kernighan's algorithm).
// Each iteration clears the lowest set bit, so it loops once per set bit,
// not once per total bit; faster than checking every bit individually.
function countSetBits(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1; // clear the lowest set bit
    count++;
  }
  return count;
}

// Find the single number that appears once among duplicates that all appear twice.
// XOR-ing all elements cancels every pair (x ^ x === 0), leaving the unique value.
function singleNumber(nums) {
  return nums.reduce((acc, n) => acc ^ n, 0);
}

Alternative Approaches

Most bit tricks have an arithmetic or data-structure-based equivalent that's more readable but slower or more memory-hungry. Checking a power of two can be done with Math.log2(n) % 1 === 0, but this introduces floating-point precision risk. Finding a unique element among duplicates can be done with a Set or frequency map in O(n) time and O(n) space, versus the XOR trick's O(1) space. Bitmask DP for subset-based state can be replaced with arrays of booleans or actual Set objects, at the cost of more memory and typically slower access.

The general tradeoff: bitwise tricks are faster and more memory-efficient, but less readable to someone unfamiliar with the specific trick, so in an interview, it's worth briefly explaining why a bit operation works, not just using it silently.

Common Mistakes

• Confusing >> (sign-propagating) with >>> (zero-fill) right shift: using the wrong one on negative numbers produces unexpected results.
• Forgetting JS bitwise operators coerce to 32-bit signed integers: bit tricks can silently break on numbers larger than 2^31 - 1.
• Off-by-one errors in shift amounts: shifting by the wrong count when building or reading a mask, e.g. 1 << i vs 1 << (i - 1).
• Assuming x & (x - 1) works on zero or negative numbers without checking: always validate the input domain (e.g. isPowerOfTwo must exclude non-positive numbers).
• Using bit tricks where they hurt readability without justification: a clever one-liner that the interviewer can't follow may cost you more than it gains; explain the trick.

Pattern Summary

Bit manipulation replaces loops and auxiliary data structures with constant-time operations on a number's binary representation, at the cost of readability. It shines whenever a problem hints at powers of two, XOR-based cancellation, or a small enough state space to encode as a bitmask; always be ready to explain the underlying binary reasoning, not just recite the trick.