227: Bit Manipulation, Bitmasks, XOR, Subsets, and Integer Caveats

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply bit operations in a realistic implementation;
explain and apply XOR identities in a realistic implementation;
explain and apply power-of-two tests in a realistic implementation;
explain and apply subset masks in a realistic implementation;
explain and apply DP over masks in a realistic implementation.

These are implementation skills, not just vocabulary. You should be able to state the input constraints, choose a representation that fits them, explain the invariant that makes the algorithm correct, and identify where the representation stops being safe.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to track flags, compare state, identify a missing value, enumerate combinations, or represent a small set compactly. It does not have to have used bitwise operators. The point is to connect the technique to a real constraint rather than memorize a clever-looking expression.

The same reasoning applies in an interview-sized problem and in production data processing: start with the contract and the constraints, then select the representation. A bitmask can be elegant when the universe is small and fixed; it can be a source of silent bugs when values exceed the language's bitwise range or when a reader cannot tell what each bit means.

Terminology

Bit operations: AND tests common bits, OR sets bits, XOR toggles or detects differences, and shifts move bit positions. A mask uses those operations to set, clear, or test a feature at a known position.
XOR identities: x ^ x = 0, x ^ 0 = x, and XOR is associative and commutative. Together, these properties support single-unpaired-value and parity-style problems when the input contract guarantees the required pairing behavior.
Power-of-two tests: For a positive integer x, x & (x - 1) clears the lowest set bit. Therefore, x is a power of two when it has exactly one set bit. The positivity check matters because zero also satisfies x & (x - 1) === 0.
Subset masks: For n small enough, integers from 0 through 2^n - 1 encode subsets; bit i says whether item i is included. Treat this as a precise engineering representation, not merely vocabulary. There are 2^n masks, so enumeration is exponential.
DP over masks: Bitmask DP represents small sets of visited or assigned items and can solve traveling- or assignment-like problems for n around the low twenties, depending on the transitions and the available memory. The state count is commonly O(n2^n) rather than polynomial.
JavaScript numeric caveat: Standard bitwise operators operate on 32-bit signed values. JavaScript first converts operands to that representation, which means values above bit 31, and especially values beyond the safe integer range, need explicit treatment.

Mental model

Treat Bit Manipulation, Bitmasks, XOR, Subsets, and Integer Caveats as a design problem with observable inputs, outputs, invariants, and failure modes. Bits provide compact state and constant-time operations on a fixed set of positions, but compactness is not the same as clarity or unlimited capacity. JavaScript bitwise operators coerce operands to signed 32-bit integers, so numeric assumptions must be explicit. A strong implementation makes the bit-to-meaning mapping visible, narrows uncertainty at the boundary, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

For example, if bit 0 means isDraft and bit 1 means isArchived, the mask 0b0011 is not self-documenting by itself. Named constants and tests for each flag make the invariant reviewable. The model also has a limit: a bitmask represents positions in a known finite universe, not arbitrary business data, and a JavaScript Number bitwise expression does not preserve arbitrary-width integer precision.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a clever expression or a library call. First state what must remain true. Then choose the mechanism that enforces it. If the requirement is “return the one value that appears once while every other value appears twice,” the pairing guarantee is part of the contract; without it, XOR alone cannot identify an answer reliably.

Deep dive

1. Bit operations

AND tests common bits, OR sets bits, XOR toggles or compares bits, and shifts move bit positions. A typical flag mask uses 1 << position: (state & mask) !== 0 tests a flag, state | mask sets it, and state & ~mask clears it. These operations are constant time for the machine-sized representation, although the surrounding algorithm may still be expensive.

Decision rule: Use bit operations deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. In application code, an object or Set may communicate named state better; in a tight algorithm with a small fixed universe, a mask can make membership and transitions both simple and efficient.

2. XOR identities

x ^ x = 0 because equal bits differ nowhere, and x ^ 0 = x because zero changes no bit. XOR is associative and commutative, so the order of the operands does not affect the result. This lets paired values cancel:

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

That reasoning supports the single-unpaired-value pattern in linear time and O(1) additional space, but only under the stated pairing contract. XOR is also useful for parity, because a bit is set in the result when it was set an odd number of times. It is not a general replacement for equality, addition, or duplicate detection when values can occur arbitrary numbers of times.

Decision rule: Use XOR identities deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. State whether negative values, repeated values, multiple unpaired values, and JavaScript's 32-bit coercion are allowed before relying on the expression.

3. Power-of-two tests

For positive integer x, x & (x - 1) clears the lowest set bit. A positive power of two has exactly one set bit, so the result is zero:

function isPowerOfTwo(x: number): boolean {
  return x > 0 && (x & (x - 1)) === 0;
}

The x > 0 guard is not optional: 0 & -1 is also zero, but zero is not a power of two. The test is O(1) for JavaScript's 32-bit bitwise representation. If the accepted values can exceed that representation, use a representation and operation whose width matches the contract, such as BigInt with BigInt operands.

Decision rule: Use power-of-two tests deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. In particular, document whether the input is an integer and whether zero, negative numbers, or values beyond the bitwise range are valid.

4. Subset masks

For n small enough, integers 0..2^n-1 encode subsets; bit i answers whether item i is included. To enumerate every subset, iterate through all masks and inspect each bit:

for (let mask = 0; mask < (1 << n); mask += 1) {
  const subset = items.filter((_, index) => (mask & (1 << index)) !== 0);
  // Process subset here.
}

There are 2^n subsets and this version inspects n positions for each one, so its time complexity is O(n2^n) and its materialized subset space is O(n) per iteration. The mask itself is compact, but the exponential count remains. Use it when n is genuinely small and the item-to-bit ordering is stable; do not mistake a fast inner loop for a scalable algorithm.

Decision rule: Use subset masks deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. A Set is often clearer when the universe is large, dynamic, or not naturally indexed from zero.

5. DP over masks

Bitmask DP represents small sets of visited or assigned items. A state such as dp[mask][last] can mean “the best cost for visiting exactly the items in mask and ending at last.” To extend it, choose an item not in mask, form nextMask = mask | (1 << next), and relax the destination state. For many traveling-salesperson-style formulations, there are O(n2^n) states and O(n) transitions per state, giving O(n^2 2^n) time and O(n2^n) space. The exact bound depends on the transition definition.

This is useful for small assignment and routing problems, often with n around the low twenties, but the boundary is hardware-, language-, and transition-dependent. The mask describes membership; the additional dimensions describe the information needed to make the future independent of the earlier path.

Decision rule: Use DP over masks deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Compare it with backtracking, branch-and-bound, matching, or a problem-specific polynomial algorithm when the input grows or the state requires more than a compact mask.

6. JavaScript numeric caveat

Standard bitwise operators operate on 32-bit signed values. For example, 1 << 31 produces a negative signed value, and shifting beyond the supported positions does not create an arbitrary-width mask. Number itself can represent many larger integer values, but bitwise operators do not preserve those widths. Use BigInt bit operations or another representation for larger bitsets, and do not mix BigInt with Number in an operation without an explicit conversion.

That conversion boundary is easy to miss in code that passes ordinary tests and fails only for a high flag position or large identifier. Test the highest supported bit, document the supported width, and use BigInt consistently when the domain requires it. Also remember that BigInt and Number have different APIs and cannot be compared or added indiscriminately.

Decision rule: Use the JavaScript numeric caveat deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Select Number, BigInt, a typed array, or a Set based on value range, interoperability, serialization, and readability.

Worked example

Consider an interview-sized problem and a production data-processing problem. In both cases, begin by writing the requirement in one sentence, listing the input and output contracts, and identifying which concept owns each failure mode. For a bitmask problem, also write down the bit ordering, maximum supported bit position, and whether the values are ordinary numbers or BigInts. Those details are part of correctness, not implementation trivia.

The important architectural move is separation: parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. A compact algorithm inside the wrong layer is still a poor design. Mixing these concerns makes a happy-path demo look shorter while making malformed input, retries, concurrency, and numeric edge cases harder to reason about.

The source example is intentionally small:

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

This function scans the input once, so it is O(n) time and O(1) additional space. Its invariant is that after processing each element, answer is the maximum of all values seen so far. It is not a bit-manipulation solution, and that is worth calling out: preserve a supplied example, but do not claim that a generic maximum scan demonstrates XOR, subset masks, or bitmask DP. A topic-specific implementation must be chosen only after the requirement establishes which state needs to be represented.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this function, the empty-array behavior is a contract decision rather than something Math.max solves automatically: returning 0 may be valid only if the domain allows it as the empty result. In a service, missing input should usually be rejected at the boundary; a dependency failure should be represented as an error rather than silently converted into a number. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For bit-packed state, ask what happens when a new flag is added, when two services disagree about bit positions, when serialized values cross a language boundary, and when a value exceeds JavaScript's 32-bit bitwise range. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and network input is untrusted. A client-side permission bit can control presentation, but it must not stand in for server-side authorization.

Guided lab

Solve single-number, count-set-bits, subset generation, and one small bitmask-DP assignment problem. Demonstrate the 32-bit JavaScript coercion limit with a value above bit 31. For each solution, record the invariant and the time and space complexity. For the single-number exercise, state the pairing guarantee before using XOR. For subset generation and DP, record n and the resulting 2^n state growth so the exponential cost is visible rather than implicit.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

Edge cases and failure modes

Bit operations: test absent flags, malformed input, duplicate flag updates, ordering or concurrency where applicable, and the smallest and largest credible bit positions. Verify set, clear, and test operations independently.
XOR identities: test absence, malformed input, duplicates, ordering or concurrency where applicable, and the smallest and largest credible values. Include a case with two unpaired values to confirm that the pairing contract is real rather than assumed.
Power-of-two tests: test zero, one, negative values, non-integers, malformed input, and values at the supported numeric boundary. Zero is the common false positive when the positivity guard is omitted.
Subset masks: test n = 0, duplicate items, an unstable item ordering, malformed input, and the largest supported n. Confirm that the implementation does not silently overflow its mask representation.
DP over masks: test an empty assignment, impossible transitions, duplicate items, malformed input, ordering or concurrency where applicable, and the smallest and largest credible n. Watch both runtime and memory because 2^n grows quickly.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Forgetting that JavaScript bitwise operators coerce to signed 32-bit integers, or mixing BigInt and Number without an explicit boundary.
Treating a mask as self-documenting when the meaning of each bit, supported width, and serialization format have not been specified.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. For a bit bug, print values in binary as well as decimal, inspect the operand types, and check the highest set bit. For a DP bug, inspect one mask transition, verify that the selected item was not already present, and compare the state count against the expected 2^n bound.

Interview questions

What problem do bit operations solve, and what trade-off or failure mode would make you choose a different approach?
What problem do XOR identities solve, and what trade-off or failure mode would make you choose a different approach?
What problem do power-of-two tests solve, and what trade-off or failure mode would make you choose a different approach?
What problem do subset masks solve, and what trade-off or failure mode would make you choose a different approach?
What problem does DP over masks solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Bit Manipulation, Bitmasks, XOR, Subsets, and Integer Caveats to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Include its time and space complexity, and explain why its numeric representation is valid for the stated constraints.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.