Bit Manipulation Questions at Trading Firms

Bit manipulation questions test whether a candidate can replace a loop with a hardware word operation inside a latency-sensitive system.

Bit manipulation questions at trading firms test whether a candidate can use the machine's native word operations to replace a loop, which matters at firms measuring latency in nanoseconds rather than milliseconds. A bitset that finds the best occupied price level without scanning, an XOR trick that finds one unmatched trade id in a stream of paired events, a bitmask that represents which venues an order is eligible to route to, and a power-of-two rounding trick for a fixed-size memory allocator are the four shapes that come up most.

State the problem precisely: a fixed range of price ticks is represented as a single bitset where bit i is set if any order currently rests at tick i, and the system must repeatedly answer which occupied tick is closest to the top of the book. Scanning the bitset bit by bit costs O(w) for a w-bit word, but a hardware bit-scan instruction, exposed in most languages as a find-first-set or count-leading-zeros primitive, answers the same query in a small constant number of cycles by operating on the whole word at once rather than one bit at a time.

The follow-up asks what happens once the price range spans more ticks than fit in a single machine word, which is the realistic case for any instrument with a wide trading range. The candidate is expected to propose a hierarchical bitset, sometimes called a bitmap index or a summary bitset, where a smaller top-level word tracks which word-sized chunks of the full range contain at least one set bit, letting the search skip directly to the relevant chunk before scanning within it, turning an O(range divided by word size) scan into two constant-time lookups.

State the problem precisely: a stream of trade lifecycle events pairs every new order id with exactly one terminal event, either a fill or a cancel acknowledgment, except for a single order whose terminal event is missing from a batch under investigation, and the task is to find that one id. XOR-ing every id in the batch together cancels every id that appears exactly twice, since a value XOR'd with itself is zero, leaving only the one id that appears an odd number of times, which solves the problem in O(n) time and O(1) space with no hash set required at all.

The follow-up asks what changes if two ids can be missing their terminal event rather than one, since XOR-ing everything together no longer isolates a single value cleanly. The standard extension splits the combined XOR result by any bit where it is set, which must differ between the two missing ids, and XORs each partition separately to recover both values, and the interviewer is checking whether the candidate can extend the trick rather than abandon it for a hash-based approach the moment the clean single-value case breaks.