Bits and math

Bit tricks help when a problem has a matching property. XOR cancels pairs: x XOR x = 0, and x XOR 0 = x. In Single Number, every value that appears twice cancels out, leaving the one that appears once. That relies on the problem's promise that everything else appears exactly twice.

A bitmask can stand for a subset of a small set: bit i is 1 when item i is in. Setting, clearing, and testing bits give you set operations. Trying every mask still takes exponential time; a compact representation doesn't reduce the number of subsets.

x & (x - 1) clears the lowest 1 bit of a positive unsigned integer. In Rust, be careful with zero and subtraction. Shifts must stay within the integer's width. Shifting signed numbers right, or letting arithmetic overflow, can change the result you meant.

Math can often replace simulation. Euclid's algorithm uses gcd(a, b) = gcd(b, a mod b) for positive b. Fast exponentiation squares repeatedly, using the exponent's binary digits. Modular arithmetic groups numbers by remainder, but decide how to handle negative remainders.

For counting problems, decide the model first. Does order matter? Can items repeat? Can you tell the items apart? A binomial coefficient counts choices where order doesn't matter; permutations count arrangements. The wrong model can give a neat formula for the wrong thing.

Number sizes matter no matter how fast the algorithm is. An O(n) algorithm can still overflow when adding n values or multiplying two coordinates. Convert to a wider type before the operation, not after. When the answer is wanted modulo M, apply the modulo where the math allows it. Division needs a modular inverse, which doesn't always exist.

Practice: LC 136 Single Number, LC 191 Number of 1 Bits, LC 338 Counting Bits, LC 50 Pow, LC 78 Subsets, LC 201 Bitwise AND of Numbers Range.

Check your understanding: Which formula makes the trick work? Which promise about the input does it rely on? Would values appearing three times instead of twice break it?