TAOCP 7.1.3 Exercise 216

Working

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 216. ▶ [M26] [M26] Given n-bit integers x1, . . . , xm ≥0, n ≥λm, compute in O(m) steps the least y > 0 such that y /∈{a1x1+· · ·+amxm | a1, . . . , am ∈{0, 1}}, if λx takes unit time.

Verified: no
Solve time: 1m34s

Working