Bit manipulation and modular arithmetic

CS · Chapter 711 min readAsked at Hudson River Trading, Jump, Tower, Optiver

Assumes Core techniques: binary search on the answer, two pointers, sliding windows.

After this lesson you should be able to

  • Use the standard bit tricks and say what each does.
  • Apply XOR properties to find a missing or unpaired element.
  • Compute a large power modulo mm efficiently.

Bit manipulation turns up in two places: as a puzzle in interviews, and as a genuine optimisation on a latency-sensitive path where a branch or a division is too expensive. Both reward knowing a short list of identities cold.

ExpressionDoesNote
x & (x−1)x \,\&\, (x-1)Clears the lowest set bitLoop on it to count set bits
x & −xx \,\&\, -xIsolates the lowest set bitThe basis of the Fenwick tree
x & (x−1)==0x \,\&\, (x-1) == 0Tests for a power of twoCareful with zero
x⊕yx \oplus yDiffers where they differSelf-inverse: x⊕x=0x \oplus x = 0
x≪kx \ll k, x≫kx \gg kMultiply or divide by 2k2^kBeware sign on right shift
x ∣ (1≪k)x \,|\, (1 \ll k)Sets bit kkAnd & ∼(1≪k)\&\,\sim(1 \ll k) clears it
Table 7.1 · The tricks. The second row is the one with a real use: x & −xx \,\&\, -x works because the two’s-complement negation flips every bit above the lowest set bit and leaves it alone, so the AND keeps exactly that bit.

Why XOR solves the pairing puzzles. XOR has three properties that together do all the work: it is its own inverse, it is commutative and associative, and zero is the identity. So XOR-ing a whole collection cancels everything that appears an even number of times, whatever the order, and leaves whatever appeared an odd number of times. "Find the element that appears once among pairs" and "find the missing number from 1 to nn" are the same problem, both solved in one pass with constant memory — and no sorting, hashing or extra space.

Example 7.2

An array holds every number from 11 to nn except one. Find the missing one in O(n)O(n) time and O(1)O(1) space, two ways.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    sum: n(n+1)2−∑ai,XOR: (⨁1ni)⊕(⨁ai)\text{sum: } \frac{n(n+1)}{2} - \sum a_i, \qquad \text{XOR: } \left(\bigoplus_{1}^{n} i\right) \oplus \left(\bigoplus a_i\right)
  2. Substitute
    n=5, a=[1,2,4,5]n = 5, \ a = [1, 2, 4, 5]
  3. Solve
    sum: 15−12=3\text{sum: } 15 - 12 = 3
  4. XOR: (1⊕2⊕3⊕4⊕5)⊕(1⊕2⊕4⊕5)=3\text{XOR: } (1\oplus2\oplus3\oplus4\oplus5) \oplus (1\oplus2\oplus4\oplus5) = 3
  5. Answer
    3, by either method3, \text{ by either method}

Sanity check. The XOR version is preferable in production because the sum can overflow for large nn while the XOR cannot. That is exactly the kind of detail a low-latency interviewer is looking for.

Proposition 7.3

Modular arithmetic

Addition and multiplication commute with taking a remainder, so you can reduce at every step and never overflow. Division does not: dividing modulo mm means multiplying by a modular inverse, which exists only when the divisor and mm are coprime.

Holds when

  • (a+b) mod m=((a mod m)+(b mod m)) mod m(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m, and likewise for products.
  • Fermat: when mm is prime, a−1≡am−2(modm)a^{-1} \equiv a^{m-2} \pmod m.
  • Negative remainders differ by language — C and Python disagree, and it is a real source of bugs.

The rest of this lesson is in Premium

You have read the opening. 12 more sections follow, including 4 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Complexity: reading it off, and deriving it in full, free.

Bit manipulation and modular arithmetic · QuantMax