Bit Manipulation: XOR Tricks and Binary Thinking

Bit manipulation questions look like trivia and are actually a fluency check: integers are bit vectors, and certain problems collapse to one line when you treat them that way. Trading-systems code — flags, exchange protocols, fast sets — leans on these habits daily.

The operators and the idioms

AND &, OR |, XOR ^, NOT ~, shifts << >>. Shifting left/right multiplies/divides by 2 — binary's version of the decimal point. The idioms worth having at your fingertips:

• Test bit $k$: x & (1 << k) · set: x | (1 << k) · clear: x & ~(1 << k)
• x & (x-1) clears the lowest set bit. Corollaries: x & (x-1) == 0 tests power-of-two (one line, constant time); counting set bits by repeated clearing runs in O(bits-set) — Kernighan's trick.
• x & (-x) isolates the lowest set bit — the indexing engine inside Fenwick trees.
• Even/odd is x & 1; the parity arguments of the modular-arithmetic lesson, at machine speed.

XOR: the star of the show

XOR is addition mod 2, so it's associative, commutative, self-inverse ($a \oplus a = 0$, $a \oplus 0 = a$). Those three properties generate the classic one-liners:

• Missing number: array holds $0..n$ except one — XOR everything with $0..n$; pairs annihilate, the missing value remains. (The Gauss-sum approach from the series lesson works too; XOR avoids overflow concerns — say both.)
• Single number: every element appears twice except one → XOR the array.
• Swap without a temp (a^=b; b^=a; a^=b) — a party trick, but explaining why it works tests the identities.
• The deeper appearances: XOR is the backbone of parity checks and RAID recovery, of hashing mixes, and of the winning strategy in Nim (the game-theory adjacent puzzle: XOR the pile sizes; nonzero means the mover wins) — worth knowing exists, occasionally asked whole.

Bitmasks as sets

An integer is a set over a universe of ≤ 64 items: membership, union, intersection are single instructions. Iterating for mask in range(1 << n) enumerates all subsets — the backtracking lesson's $2^n$ tour in loop form — and "DP over subsets" (state = mask of assets already chosen, say) is a standard technique for small-$n$ allocation problems. Practical notes for Python specifically: integers are arbitrary-precision (no overflow, unlike C++/Java — a difference interviewers probe), and bin(x).count("1") or x.bit_count() (3.8+/3.10+) counts bits without cleverness.

Floats are bits too

One systems-flavored fact with real interview mileage: IEEE-754 doubles are 64 bits — sign, 11-bit exponent, 52-bit mantissa. Consequences: integers above $2^{53}$ aren't exactly representable (silent P&L bugs when ids or nanosecond timestamps pass through floats — a genuine production incident class), and 0.1 + 0.2 != 0.3 (the Python lesson's warning, now with its mechanism). "Why do we store prices in integer ticks?" — this paragraph is the answer.

The interview version

"An array of 2n+1 ints, every value appears twice except one — find it, O(n) time O(1) space." — XOR sweep, with the two-property justification (self-inverse + commutativity) narrated. "Check if a number is a power of two." — x > 0 and x & (x-1) == 0, and explain the borrow that makes it work. These are fast questions; the grade is whether the answer arrives in seconds with the why attached — pattern recognition, not derivation, which is what this lesson is for.