Bit Manipulation

Bit Manipulation

Every integer you have ever used is secretly a little array of switches. We usually ignore that and treat numbers as quantities, but the moment you start thinking of an int as a row of bits, a whole category of problems collapses from clever to trivial. Bit manipulation is the habit of operating on those switches directly, and it buys you two superpowers: arithmetic-free tricks with XOR that make duplicates vanish, and the ability to pack an entire set of yes/no facts into a single number that the hardware can twiddle all at once.

The first superpower comes from XOR's two magic identities: a ^ a = 0 and a ^ 0 = a. Anything XOR'd with itself cancels to nothing, and XOR'ing with zero leaves you unchanged. So if you XOR a whole pile of numbers together, everything that appears an even number of times annihilates itself, and whatever is left standing is the odd one out.

The lonely number

The canonical demonstration: an array where every value appears exactly twice except one, and you want the loner. No sorting, no hashmap, no second pass. Just XOR everything together.

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x        # pairs cancel to 0; the lonely value survives
    return result

The reason it works is worth seeing bit by bit. XOR on a column of bits is just parity: it is 1 when an odd number of inputs are 1. Every value that appears twice contributes an even count to every column, so it leaves no trace. The one unpaired value is the only thing that can flip a column to odd, so the surviving bits spell out exactly that value. It runs in one linear pass with a single integer of memory.

The same trick, barely disguised, finds a missing number: XOR all the indices 0..n together with all the values, and every number that is present cancels against its index, leaving only the one that is absent. If it smells like "everything pairs up except the thing I want," XOR is probably the whole solution.

In the wild: an integer as a compact set

XOR is the flashy trick, but the workhorse use of bit manipulation is encoding a set as an integer, one bit per possible member. This is exactly how filesystem permissions work: read is 1, write is 2, execute is 4, and a file's mode is just those bits OR'd together. The four fundamental operations become one-liners:

READ, WRITE, EXEC = 1, 2, 4

mode = READ | WRITE          # grant read and write   -> 011
can_write = mode & WRITE     # test a bit (nonzero if set)
mode = mode | EXEC           # set a bit               -> 111
mode = mode & ~WRITE         # clear a bit             -> 101
mode = mode ^ EXEC           # toggle a bit            -> 001

Test with AND, set with OR, clear with AND NOT, toggle with XOR. Because the whole set lives in one number, you compare or combine two sets, union with |, intersect with &, in a single instruction, no loop over members. That compactness is why the same idea shows up as feature flags, capability bits, network-protocol headers, chess engines that store a board as a 64-bit "bitboard," and, most powerfully, in bitmask dynamic programming: when a problem has a small set of items (say up to about 20) and you need to track which subset you have used, you let an integer be the subset and iterate over all 2^n of them. The state that would need a set becomes a single array index. It is genuinely the same pattern as the permissions flags, just used as a DP dimension instead of a file mode.

A couple of bit tricks earn their keep often enough to memorize: x & (x - 1) clears the lowest set bit (loop it and count the iterations to count set bits), x & -x isolates the lowest set bit, and x & (x - 1) == 0 tests whether x is a power of two.

The trigger

You are toggling or checking presence across a small, fixed set of things, or a problem screams "everything pairs up except one." The tells are a small universe of items you want to track as a subset, permission or flag style state, or a counting or matching problem where identical things should cancel. If you find yourself reaching for a set over a tiny fixed range, or a hashmap just to spot the unpaired element, a bitmask or an XOR is usually smaller and faster.

Where it shows up

• XOR cancellation: single number, missing number, the two non-repeating numbers, checksums and parity bits.
• Bitmask as a set: permissions and feature flags, protocol headers, bitboards, bloom-filter style membership.
• Bitmask DP: traveling salesman and assignment problems, subset-sum and covering problems with a small item count.

Where it bites

Operator precedence is the great trap: &, |, and ^ bind looser than comparison in C-like languages and Python, so x & 1 == 0 parses as x & (1 == 0) and silently does the wrong thing. Parenthesize religiously. Signed integers and arbitrary-width ints add their own surprises, negative numbers, sign extension on right shifts, Python's unbounded integers behaving unlike a fixed 32 or 64-bit word, so know your language's model before you rely on a bit landing where you think. And off-by-one on shift amounts, 1 << i versus 1 << (i - 1), is the kind of bug that hides until exactly the wrong input.

When it is the wrong tool

The elegance evaporates the moment your set outgrows a machine word. Past 64 elements a single integer cannot hold the mask, and bitmask DP detonates well before that, since 2^25 states is already tens of millions, so for large universes reach for an actual set, a bitset array, or a hashmap. Bit tricks are also the wrong tool when they cost more in readability than they save in speed. A clever hack in place of plain arithmetic that the compiler would have optimized anyway is a maintenance landmine, not a win. And a bitmask encodes only presence or absence; the instant you need counts or richer per-element data, it is the wrong container and you want a proper map.

Its neighbors

It is the enabling trick behind Dynamic Programming whenever the state is "which subset have I used," a partnership so common that "bitmask DP" is a named technique. It overlaps Backtracking and Subsets, since iterating a mask from 0 to 2^n - 1 enumerates every subset without recursion. And it is the low-level, small-universe alternative to Hashmaps and Frequency Counting, which remain the right general-purpose tool the moment your keys are large, sparse, or not integers at all.