Bit Manipulation, Mathematics, and Probability

What may the algorithm forget?

An event stream contains integer IDs. Every ID should appear exactly twice, once when work begins and once when it ends, but one record has lost its mate. A frequency map will find it. So will this:

unpaired = 0
for id in events:
  unpaired = unpaired ^ id
return unpaired

The second solution looks like a trick until its loss of information is made explicit. XOR preserves only whether each value occurs an odd or even number of times. Equal pairs cancel, so the one odd occurrence survives. Exact counts, order, and positions disappear—and this prompt needs none of them.

Now change one sentence: every ordinary ID appears three times. The same loop is wrong. The code has not changed, but its permission to forget has.

Bit manipulation, modular arithmetic, combinatorics, and probability are often taught as a cabinet of formulas. They are more useful as variations on one question: what can be discarded while the answer remains determined? A compact model is earned by answering four things:

1. What does the stored value mean?
2. What information does it discard?
3. Why do the updates preserve that meaning?
4. Which changed constraint would make the discarded information relevant?

The previous chapter merged histories into DP states. Here the compression may be smaller still: a set becomes bits, a long process becomes a residue, a family of objects becomes a count, or a distribution becomes an expectation. In every case, the boundary of the model matters more than the clever expression.

A mask remembers membership, not history

A bitmask represents a fixed dictionary of Boolean facts. If bit i means “task i is complete,” the common operations read almost as sentences:

test i:       mask & (1 << i)
set i:        mask | (1 << i)
clear i:      mask & ~(1 << i)
toggle i:     mask ^ (1 << i)
count facts:  popcount(mask)

The dictionary is part of the invariant. A bit cannot mean a database shard in one transition and a permission in another. Nor can a mask answer when a task completed, how many times it ran, or which task preceded it. If any of those facts affect a future choice, the state needs to retain them elsewhere.

This is why a bitmask can be an honest DP state:

dp[mask] is the lowest cost of completing exactly the tasks whose bits are set in mask.

That state is sufficient only if two orders that complete the same set have identical legal futures. If the next cost depends on the most recent task, the honest state is dp[mask][last]. The extra dimension puts the lost fact back.

For n fixed items, the integers from 0 through (1 << n) - 1 enumerate all subsets. Materializing each subset takes O(n * 2^n) time:

for mask in 0 .. (1 << n) - 1:
  for i in 0 .. n - 1:
    if mask & (1 << i):
      include items[i]

A 64-bit word may hold roughly 60 usable membership flags; it cannot make 2^60 states tractable. Separate the storage question from the enumeration question. A large bitset may still be an excellent compressed vector even when visiting every possible bitset is absurd.

Two low-bit identities are worth deriving rather than memorizing. mask & (mask - 1) removes the least significant set bit because subtracting one flips that bit and every lower zero. In a two’s-complement representation, mask & -mask isolates the same bit. The first identity gives the familiar power-of-two test:

x > 0 && (x & (x - 1)) == 0

The positive guard belongs to the proof. Zero also satisfies the bit expression, but it has no set bit.

The implementation boundary is the language’s integer model. Establish the word width and signedness before shifting; use a literal of the required width; parenthesize shifts inside larger bit expressions; and check what the language specifies for negative values and out-of-range shift counts. The algebra does not excuse undefined, trapping, or silently truncated code.

XOR remembers parity, not frequency

The opening loop follows from three identities:

• x ^ x = 0;
• x ^ 0 = x;
• XOR is associative and commutative.

Those identities permit reordering the stream conceptually until every pair sits together and vanishes. The algorithm is O(n) time and O(1) auxiliary space because the prompt asks for exactly the information XOR preserves.

They also explain its limits. Three copies of x reduce to x, not zero. If every ordinary value appears three times, count each bit modulo three:

for bit in 0 .. word_width - 1:
  ones = number of input values with this bit set
  if ones % 3 != 0:
    set bit in answer

The new invariant is per-bit residue, not value-level parity. Reconstructing a negative answer may require deliberate handling of the sign bit in languages whose integers do not naturally wrap at the chosen width.

If two values are unique while all others appear twice, XORing the stream produces combined = a ^ b. Because a != b, combined has a set bit where they differ. Isolate one such bit and partition the input on it:

split = combined & -combined

Every equal pair enters the same partition and cancels. The two unique values enter different partitions and survive. This second pass does not undo the compression; it finds the one bit of information needed to separate the two answers.

XOR is therefore a poor substitute for a frequency map and an excellent parity operator. The multiplicity promise decides which description is true.

A residue remembers position in a cycle, not magnitude

Modulo m, integers that differ by a multiple of m are interchangeable for addition and multiplication. That lets a huge count retain only its residue, or a billion-step process retain only its position in a period. It does not make all arithmetic safe automatically.

Consider fast doubling for a very large Fibonacci index. Store the pair (F(k), F(k + 1)) and derive twice the index with:

F(2k)     = F(k) * (2 * F(k + 1) - F(k))
F(2k + 1) = F(k)^2 + F(k + 1)^2

The pair is a complete recurrence state, so following the binary decomposition of n reaches it in O(log n) doubling steps. If the requested answer is modulo m, each pair may contain residues rather than full Fibonacci values. Every formula preserves the pair’s meaning under congruence.

Three implementation hazards remain.

First, % m happens after its operand is evaluated. In a fixed-width type, a * b can overflow before the remainder is taken. Reducing a and b bounds them but may still leave a product near m^2. Use a sufficiently wide type, an overflow-safe modular multiplication routine, or arbitrary precision when the constraints and language allow it.

Second, languages disagree about negative remainders. Normalize a possibly negative result when the required representative is in [0, m):

mod(x, m) = ((x % m) + m) % m

Third, ordinary division does not survive the compression. Replacing division by multiplication with a modular inverse is valid only when the inverse exists: b must be relatively prime to m. For prime m and b not divisible by m, Fermat’s little theorem provides one route; otherwise the algorithm may need a recurrence that avoids division.

Cycle detection makes the same promise in a different form. Repeated state in a deterministic transition implies repeated future behavior. But “state” must include every future-relevant fact. A robot’s grid position alone does not prove a cycle if its direction or remaining energy has changed. A residue is useful only after the period has been proved, and a repeated state is useful only after state identity is complete.

A formula remembers how many, not which ones

An r by c grid with moves only right and down gives a clean example of combinatorial compression. Every path contains r - 1 down moves and c - 1 right moves. Choosing which positions contain the down moves determines the entire path:

C(r + c - 2, r - 1)

For a 3 by 4 grid, that is C(5, 2) = 10. The formula is a compressed enumeration: every valid path maps to one choice of two positions, and every such choice maps back to one valid path. That bijection is the correctness argument.

Put one blocked cell in the grid and the argument fails. Some move sequences now cross an illegal position. The count must remember location again:

if cell is blocked:
  ways[row][col] = 0
else:
  ways[row][col] = ways[row - 1][col] + ways[row][col - 1]

The DP is not a more sophisticated answer to the same model. It is the answer to a changed model in which position can no longer be discarded.

Before applying a counting formula, decide whether order matters, repetition is allowed, objects are distinct, and later choices depend on earlier ones. For example, A, B, C have 3! permutations, while A, A, B have 3! / 2! distinct permutations because exchanging the two A values creates nothing new. If the result is required modulo m, the division again needs a valid modular inverse or a computation that performs exact cancellation before reducing.

Randomness needs a named sample space

“Choose randomly” is not an algorithm. It must specify which outcomes should be equally likely and how the implementation creates that distribution.

To shuffle an array uniformly, process positions from right to left. At position i, choose j uniformly from the inclusive range [0, i] and swap:

for i from n - 1 down to 1:
  j = uniform_integer(0, i)
  swap(a[i], a[j])

At the first step, every element has probability 1/n of occupying the final position. Conditioned on that choice, the same argument applies to the remaining prefix. Multiplying those conditional probabilities gives 1/n! for every permutation. Choosing from the whole array on every step, or sorting by a random key, does not have this proof and can be biased.

That conditional language is essential. The general rule is

P(A and B) = P(A) * P(B | A)

Only when B is independent of A may the second factor become P(B). Sampling without replacement, retry policies whose state changes, collision questions, and randomized algorithms all punish casual multiplication.

The sample space must also match the requested output. A probability may need an exact fraction, a floating-point value within a tolerance, or a residue modulo a prime. Those are different implementation contracts. For simulation, name the estimator, the source of randomness, the number of trials, and the uncertainty; empirical frequency is not an exact proof.

Expectation can discard the distribution

Suppose n requests are assigned independently and uniformly to n shards. How many shards are expected to receive no request? The emptiness events are dependent, so multiplying their probabilities would be a mistake. Expectation allows a different compression.

Let I_i be 1 when shard i is empty and 0 otherwise. The empty-shard count is I_1 + ... + I_n, and linearity gives:

E[empty shards] = E[I_1] + ... + E[I_n]
                = n * P(one particular shard is empty)
                = n * ((n - 1) / n)^n

Linearity of expectation does not require the indicators to be independent. It answers the average count while discarding the full distribution: it does not reveal the probability that more than half the shards are empty, the variance, or a tail bound. If capacity planning needs those facts, expectation alone has forgotten too much.

Put the contract under pressure

Before coding a compact solution, say its contract in ordinary language. For a mask solution, a defensible explanation might be:

There are at most 16 tasks. Bit i means task i is complete, and a transition sets one additional bit. Order is intentionally discarded because future eligibility depends only on the completed set. If it depended on the last task, I would add that task to the state. There are 2^n states.

Then change one promise and notice what breaks:

• Ask for arrival order after storing only membership in a mask.
• Change paired values to triples after choosing XOR cancellation.
• Add direction to a bounded motion process after detecting cycles by position.
• Add obstacles after replacing grid paths with a binomial coefficient.
• Ask for a tail probability after calculating only an expectation.

Each variation makes previously discarded information observable. Repairing the solution means restoring that information—not decorating the same formula with another edge case.

Compact representations are valuable because they remove work. They are trustworthy because their losses are named. Once the meaning, preservation argument, discarded facts, numeric boundaries, and cost are visible, a bit expression or formula stops being a trick and becomes an algorithm another engineer can defend.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 39: Arrays and Strings
• Chapter 48: Dynamic Programming
• Chapter 50: Pattern Selection and Proof