Bit Manipulation Fundamentals

Every integer your program touches is already a row of 0s and 1s sitting in a register. Most code ignores that and treats the number as an opaque quantity — add it, compare it, print it. Bit manipulation is the practice of reading and writing those individual 0s and 1s directly, because some problems (is a flag set, is this number a power of two, pack four small fields into one word) are solved by a single CPU instruction on the bits instead of a loop over the value.

The idea: a number is a row of switches

Picture a byte as eight light switches in a row, each either off (0) or on (1), where the rightmost switch is worth 1, the next worth 2, then 4, 8, 16, and so on — each position worth double its neighbor. The number 13 is switches worth 8, 4, and 1 turned on: 00001101. Four operations let you flip and inspect those switches directly:

• AND (&): a switch is on in the result only if it's on in both inputs. Used to test or clear specific switches.
• OR (|): a switch is on in the result if it's on in either input. Used to set switches.
• XOR (^): a switch is on in the result if it's on in exactly one input, not both. Used to flip switches and to find "what's different."
• Shift (<<, >>): slide every switch left or right, which multiplies or divides by 2 for each position moved.

Worked example: flags in an order-management system

An order carries several yes/no properties: is it a buy, is it marketable, is it a child of a parent order, is it flagged for compliance review. Instead of four separate boolean fields, pack them into one byte where each bit is a flag:

bit 0 (value 1): IS_BUY
bit 1 (value 2): IS_MARKETABLE
bit 2 (value 4): IS_CHILD_ORDER
bit 3 (value 8): NEEDS_REVIEW

An order that is a buy, marketable, and needs review — but is not a child order — sets bits 0, 1, and 3: 1 + 2 + 8 = 11, or 00001011 in binary. Checking "does this order need review" is one AND: flags & 8. If the result is nonzero, bit 3 was on. Setting the flag later is one OR: flags = flags | 8. Clearing it is an AND with the complement: flags = flags & ~8, where ~8 flips every bit of 8, turning the one bit you want to clear into the only 0 in an otherwise all-1s mask.

IS_BUY, IS_MARKETABLE, IS_CHILD, NEEDS_REVIEW = 1, 2, 4, 8

flags = IS_BUY | IS_MARKETABLE | NEEDS_REVIEW   # = 11 = 0b1011

def has_flag(flags: int, flag: int) -> bool:
    return (flags & flag) != 0

has_flag(flags, NEEDS_REVIEW)     # True  -- bit 3 is set
flags &= ~NEEDS_REVIEW            # clear bit 3: flags becomes 3 = 0b0011
has_flag(flags, NEEDS_REVIEW)     # False

Each of these operations is $O(1)$ — one machine instruction, regardless of how many flags exist, versus $O(k)$ for checking $k$ separate boolean fields one at a time. That constant-time, constant-space packing is the entire appeal: 32 flags fit in one 32-bit integer instead of 32 separate memory locations, which also means they fit in one cache line together (see The CPU Cache Hierarchy).

A second pattern: XOR to find the odd one out

XOR has a property no other operator has: x ^ x = 0 for any x, and XOR is commutative and associative, so order doesn't matter. That makes it the tool for "find the one element that doesn't have a pair." Suppose a matching engine logs order IDs twice — once on entry, once on cancel — except for one ID that only appears once because it filled instead of canceling. XOR every logged ID together: every paired ID cancels itself out to 0, and 0 XORed with the lone ID leaves the lone ID.

ids = [41, 17, 41, 9, 17]
41 ^ 17 = 56
56 ^ 41 = 17     (the two 41s have cancelled)
17 ^ 9  = 24
24 ^ 17 = 9      -- the unpaired id

This finds the answer in one pass, $O(n)$ time, $O(1)$ extra space — no hash set needed to track what's been seen.

Where this shows up

Interviewers reach for bit tricks as short, sharp coding questions — "find the single non-duplicate," "count set bits," "check if a number is a power of two" (n & (n-1) == 0, since a power of two has exactly one bit set and subtracting 1 flips every bit below it) — because they test whether you understand binary representation, not just algorithm design. In production trading systems, bitwise flags show up in order-state fields, in exchange protocol messages where a single byte encodes several boolean attributes to save bandwidth over FIX or a binary feed, and in low-level performance code where a comparison against a bitmask replaces a chain of if statements on a hot path.