Bit manipulation

Bit manipulation is a small vocabulary — test, set, clear, toggle, isolate, and count — plus a set of language contracts that decide whether any of it is well defined. This guide begins with two's complement and the asymmetric integer range that breaks absolute value at exactly one input, then covers shift semantics and the undefined behaviour that follows from over-wide shifts and signed overflow. From there it works through the techniques that genuinely matter: exclusive or as a pairing operation, masks as sets and the submask enumeration behind subset dynamic programming, and bitsets for dense membership. It also argues the negative case plainly, because most bit tricks are slower to read than the arithmetic they replace and no faster once compiled.

two's complement representation

Signed integers in almost every modern language use two's complement, where the top bit carries negative weight rather than acting as a sign flag.

This makes addition and subtraction identical for signed and unsigned values, which is why hardware implements one adder rather than two.

The top bit carries negative weight; it is not a flag.

# 8-bit: 1000_0001 is not "-1". It is -128 + 1 = -127.
(-1) & 0xFF      # 255 - all ones
(-128) & 0xFF    # 128

Interview trap. Reasoning about a sign bit as a separate flag gives wrong results for negation, shifting, and overflow.

Engineering practice. Reason in two's complement, and remember the asymmetry: the most negative value has no positive counterpart.

the asymmetric integer range

A fixed-width signed range holds one more negative value than positive, so negating the minimum overflows.

Taking the absolute value of the most negative integer returns the same negative number in wrapping arithmetic.

One more negative than positive; negating the minimum overflows.

# 32-bit: range is -2,147,483,648 .. 2,147,483,647
# abs(-2147483648) has no representable result: Java returns the same negative
# value, while C's abs(INT_MIN) has undefined behaviour.
# Python is arbitrary-precision, so the trap appears when emulating fixed width.

Interview trap. Writing a comparison or a sort key using absolute value silently breaks for that one input.

Engineering practice. Handle the minimum value explicitly in any code that negates or takes absolute values.

arithmetic versus logical shift

A right shift on a signed value replicates the sign bit, while on an unsigned value it fills with zero, and languages differ in which they provide.

Some languages choose by the operand type and others provide two distinct operators, so the behaviour must be read rather than assumed.

Signed right shift rounds towards negative infinity.

-7 >> 1        # -4 in Python (floor), not -3
int(-7 / 2)    # -3 (towards zero)
# Java: -7 >> 1 is -4; -7 >>> 1 is 2147483644. Two operators, two answers.

Interview trap. Using a signed right shift to divide by a power of two rounds towards negative infinity rather than towards zero, which differs from integer division.

Engineering practice. Check the language's operator semantics, and use explicit division when the rounding direction matters.

shift amounts outside the width

Shifting by an amount at or above the type's bit width is undefined or implementation-defined in several languages.

Some platforms mask the shift amount by the width, which turns a shift of thirty-two into a shift of zero rather than producing zero.

Some platforms mask the count, so a 32-shift becomes a 0-shift.

1 << 100         # Python: a 31-digit integer, no wrapping
# C on x86: 1 << 32 often yields 1, because the CPU masks the count to 5 bits.
# Java: 1 << 32 == 1, specified as masking. C leaves it undefined.

Interview trap. Assuming a large shift produces zero is wrong on exactly the platforms where the masking occurs.

Engineering practice. Guard shift amounts against the width, and prefer arbitrary-precision integers where the language offers them.

arbitrary-precision integers

Some languages have unbounded integers, which removes overflow but also removes the fixed width that bit tricks assume.

A left shift grows the value indefinitely, and negative values behave as if they had infinitely many leading sign bits.

Mask explicitly when emulating a fixed width.

MASK = (1 << 32) - 1
def add32(a, b): return (a + b) & MASK
def to_signed32(x): return x - (1 << 32) if x >> 31 else x

to_signed32(add32(2**31 - 1, 1))    # -2147483648

Interview trap. Porting a fixed-width mask trick to an unbounded-integer language produces values that never wrap, so the mask must be applied explicitly.

Engineering practice. Apply an explicit width mask when emulating fixed-width behaviour, and state the width in the code.

testing and setting a bit

Testing bit i uses a shifted mask and a bitwise and; setting uses or, clearing uses and with the complement, and toggling uses exclusive or.

These four operations are the vocabulary of every bit-manipulation algorithm. They are constant time on fixed-width words; arbitrary-precision integers scale with the number of stored words.

Compare the masked result against zero, not against one.

x >> i & 1        # 0 or 1 - safe
x & (1 << i)      # 0 or 2**i - compare to 0, never to 1
x |= 1 << i       # set
x &= ~(1 << i)    # clear
x ^= 1 << i       # toggle

Interview trap. Testing with a comparison to one rather than to zero fails for any bit above the lowest, since the result is a shifted value.

Engineering practice. Compare the masked result against zero, and factor the four operations into named helpers when the code has many flags.

isolating the lowest set bit

The expression combining a value with its two's complement negation isolates the lowest set bit.

Negation flips every bit above the lowest set bit and leaves it and the zeros below unchanged, so the conjunction keeps exactly that bit.

x & -x follows from two's complement, not from magic.

x = 0b101100
x & -x            # 0b100 - the lowest set bit
# -x flips every bit above the lowest set bit and leaves it and the zeros below intact.

Interview trap. Using this in an unbounded-integer language works, but reasoning about it as 'the sign bit trick' misses that it follows from two's complement arithmetic.

Engineering practice. Use it for iterating set bits, and derive it from the negation identity rather than memorising it.

clearing the lowest set bit

For a non-negative or fixed-width unsigned value, subtracting one and combining with the original clears its lowest set bit.

This makes population count run in time proportional to the number of set bits rather than to the width, which is Kernighan's algorithm.

Kernighan's loop runs once per set bit, not once per bit.

def popcount(x):
    if x < 0: raise ValueError("choose a fixed width before counting a negative value")
    n = 0
    while x: x &= x - 1; n += 1     # clears the lowest set bit
    return n

(5).bit_count()   # Python 3.10+: uses CPython's optimised implementation

Interview trap. Assuming this is faster than the hardware instruction is usually wrong, since most platforms have a single-cycle population count.

Engineering practice. Use the built-in population count where available, and keep the loop as a portable fallback.

powers of two

A positive value is a power of two exactly when clearing its lowest set bit yields zero.

The fixed-width test is constant time and needs no loop or logarithm, and it must exclude zero explicitly.

Exclude zero explicitly.

def is_power_of_two(x): return x > 0 and x & (x - 1) == 0

is_power_of_two(0)   # False - without `x > 0` this returns True
is_power_of_two(16)  # True

Interview trap. Omitting the positivity check reports zero as a power of two, which propagates into capacity and alignment logic.

Engineering practice. Combine the bit test with a positivity check, and use it for capacity rounding in hash tables and allocators.

exclusive or as pairing

Exclusive or is its own inverse, so combining a value with itself cancels, which finds the unpaired element in a list of pairs.

The operation is associative and commutative, so the order of combination does not matter and the algorithm needs one pass and constant space.

Self-inverse, associative and commutative, so order does not matter.

from functools import reduce
reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2])     # 4

# Only valid when every other element appears exactly twice. Three occurrences
# need bit-position counting modulo 3.

Interview trap. The technique works only when every other element appears exactly twice; three occurrences or two unpaired elements need a different method.

Engineering practice. State the pairing assumption, and use bit-position counting modulo three when elements repeat three times.

finding two unpaired elements

When two elements are unpaired, the combined exclusive or has a set bit where they differ, which partitions the input into two solvable halves.

Isolating any differing bit splits the elements into two groups, each containing exactly one unpaired element.

Partition on any bit where the two answers differ.

xor = reduce(operator.xor, a)          # x ^ y
bit = xor & -xor                        # a bit where they differ
g1 = reduce(operator.xor, (v for v in a if v & bit))
g2 = xor ^ g1

Interview trap. Attempting a single pass without the partition returns the combination of the two answers rather than either of them.

Engineering practice. Isolate the lowest differing bit and run the single-element algorithm on each partition.

bitmasks as sets

A bitmask represents a subset of a small universe, where union, intersection, and difference are single machine instructions.

This is what makes subset dynamic programming practical, since a state can be a set stored in a machine word.

Union, intersection and difference are single instructions.

A, B = 0b1011, 0b0110
A | B     # union        0b1111
A & B     # intersection 0b0010
A & ~B    # difference   0b1001
A.bit_count()             # size

Bounded by the word width: past ~64 elements, use a set or a bitset library.

Interview trap. The universe must fit the word width, so a set of more than about sixty-four elements needs a different representation.

Engineering practice. Bound the universe explicitly, and switch to a bitset library or a hash set beyond the word width.

enumerating subsets of a mask

The submasks of a bitmask are enumerated by repeatedly subtracting one and intersecting with the original mask.

The loop visits each submask exactly once in decreasing order, and summed over all masks the total work is three to the n.

3^n total across all masks, not 4^n.

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask
process(0)          # the loop's condition excludes the empty submask

Interview trap. Enumerating all masks and filtering for submasks costs four to the n, which is a substantial difference at typical sizes.

Engineering practice. Use the submask enumeration loop, and remember to handle the empty submask, which the loop's termination condition excludes.

iterating set bits

Iterating only the set bits costs time proportional to their count rather than to the word width.

Each iteration isolates the lowest set bit, processes it, and clears it, which visits each set bit exactly once.

Time proportional to the set bits, not the width.

while x:
    bit = x & -x
    i = bit.bit_length() - 1
    process(i)
    x ^= bit

On a 64-bit word with 3 bits set: 3 iterations, not 64.

Interview trap. Looping over every bit position and testing each wastes work proportional to the width when the mask is sparse.

Engineering practice. Use the isolate-and-clear loop for sparse masks, and a full scan only when most bits are expected to be set.

bit tricks and readability

Most bit tricks are slower to read than the arithmetic they replace and no faster once the compiler has optimised.

Compilers already turn division by a constant power of two into a shift, so writing the shift by hand buys nothing and obscures intent.

The compiler already does the easy ones.

unsigned q = n / 2;   /* an optimising C/C++ compiler emits a shift */
unsigned r = n >> 1;  /* same result, but exposes representation in source */

/* For signed negatives, division truncates toward zero while an arithmetic
   right shift rounds downward, so replacing one by the other changes meaning. */

Interview trap. Introducing bit tricks for performance without a measurement is the standard form of premature optimisation in this area.

Engineering practice. Write the arithmetic, and use bit operations where they express the intent — flags, sets, masks — rather than as an optimisation.

flags and enumerated options

Bit flags express independent options compactly, and each flag must be a distinct power of two.

Combined options are a single integer, and testing membership is a masked comparison against zero.

Powers of two, or the flags overlap.

from enum import Flag, auto
class Perm(Flag):
    READ = auto()      # 1
    WRITE = auto()     # 2
    EXEC = auto()      # 4

p = Perm.READ | Perm.WRITE
Perm.WRITE in p        # True

Consecutive integers 1, 2, 3 would make READ|WRITE indistinguishable from EXEC.

Interview trap. Assigning consecutive integers rather than powers of two makes flags overlap, so setting one appears to set another.

Engineering practice. Define flags by shifting rather than by counting, and use a language enum with flag support where available.

bitsets for large universes

A bitset packs many booleans into words and is the right structure for dense membership over a large fixed universe.

It uses one bit per element rather than one byte or one pointer, and supports whole-set operations at word granularity.

One bit per element, not one byte or one pointer.

# Membership over 10,000,000 possible ids:
#   CPython set table (1,000,000 present)  ≈ 33 MB, plus the integer objects
#   bitset of 10,000,000 bits              = 1.25 MB
# The bitset wins on density and loses badly when the universe is sparse.

Interview trap. Using a bitset for a sparse set wastes memory proportional to the universe rather than to the elements present.

Engineering practice. Choose a bitset when the density is high and the universe is bounded, and a hash set otherwise.

hashing and bit mixing

Hash functions use shifts and exclusive ors to spread input entropy across all output bits.

Without mixing, low-entropy inputs cluster in the low bits, which collide when the table size is a power of two and the index is a mask.

Mix before masking, or structured keys collide.

# Table size 1024, index = hash & 1023, identity hash:
# Ids 1024, 2048, 3072 ... all map to bucket 0.
MASK64 = (1 << 64) - 1
z = (x + 0x9E3779B97F4A7C15) & MASK64
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9 & MASK64
z = (z ^ (z >> 27)) * 0x94D049BB133111EB & MASK64
h = z ^ (z >> 31)                         # high bits now affect the bucket bits

Interview trap. Using an identity hash with a power-of-two table size makes structured keys collide systematically.

Engineering practice. Use the platform's hash, and if writing one, mix before masking rather than relying on the input's distribution.

endianness

Byte order affects any code that reinterprets an integer as bytes, which includes serialisation and network protocols.

Bit operations within a value are unaffected by endianness; only the mapping between the value and its byte sequence changes.

Byte order affects serialisation, not in-register bit logic.

(1).to_bytes(4, "big")       # b'\x00\x00\x00\x01'
(1).to_bytes(4, "little")    # b'\x01\x00\x00\x00'
1 << 3                        # 8 either way

Interview trap. Assuming bit operations are endianness-sensitive confuses two independent concerns and leads to unnecessary byte swapping.

Engineering practice. Convert explicitly at serialisation boundaries, and leave in-register bit logic alone.

overflow behaviour

Signed overflow is undefined behaviour in some languages, wraps in others, and cannot occur in arbitrary-precision ones.

Where it is undefined, the compiler may optimise on the assumption it never happens, which removes overflow checks written after the fact.

Check before, not after - the compiler may delete the after-check.

if (a + b < a) { /* overflow */ }  /* the addition is already UB in C */
if ((b > 0 && a > INT_MAX - b) ||
    (b < 0 && a < INT_MIN - b)) { /* overflow or underflow, checked before */ }

Interview trap. Checking for overflow by testing whether the result became negative is exactly the check such optimisations delete.

Engineering practice. Use the language's checked-arithmetic facilities or check before the operation rather than after.

masking to a fixed width

Emulating fixed-width arithmetic in an unbounded-integer language requires masking after every operation.

The mask keeps the low bits, and reconstructing the signed value requires subtracting the modulus when the top bit is set.

Mask, then sign-extend, or negatives come back as large positives.

MASK, SIGN = (1 << 32) - 1, 1 << 31
def wrap32(x):
    x &= MASK
    return x - (1 << 32) if x & SIGN else x

wrap32(2**31)      # -2147483648

Interview trap. Masking without the sign reconstruction produces large positive numbers where negative values were intended.

Engineering practice. Write mask and sign-extend as a pair of helpers, and test the boundary values of the emulated width.

counting and parity

Population count and parity are supported by dedicated instructions on modern hardware and exposed by most language libraries.

A fixed-width library function can compile to that instruction where available and falls back to a portable implementation elsewhere; arbitrary-precision values may require several word operations.

Call the library; it uses the platform's optimised implementation.

(0b1011).bit_count()     # 3, Python 3.10+
bin(x).count("1")        # correct, and far slower

Interview trap. Hand-rolling a population count loop is both slower and more code than calling the library function.

Engineering practice. Call the standard function, and reserve manual implementations for environments that lack one.

bit manipulation in dynamic programming

Subset dynamic programming uses masks as state indices, which is what makes travelling-salesman-style problems tractable for small vertex counts.

The mask indexes a table directly, so state lookup is an array access rather than a hash lookup.

The mask indexes the table directly.

dp = [[INF] * n for _ in range(1 << n)]
# n = 20: 1,048,576 x 20 entries. n = 25: 33,554,432 x 25 - the ceiling is hard.

Interview trap. The table size doubles with each additional element, so the approach has a hard ceiling around twenty elements.

Engineering practice. Compute the table size before implementing, and state the element limit the approach supports.

constant-time swaps and their cost

Swapping two values with exclusive or avoids a temporary, and is both slower and incorrect when the two operands alias.

If both references point to the same location the sequence zeroes it, and modern compilers already optimise the temporary away.

Zeroes the value when the operands alias.

a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j]
# With i == j this sets a[i] to 0. The ordinary swap has no such case:
a[i], a[j] = a[j], a[i]

Interview trap. Presenting the exclusive-or swap as an optimisation shows unfamiliarity with what compilers do and with the aliasing failure.

Engineering practice. Use the ordinary swap, and treat the bit version as a puzzle rather than a technique.

when bit manipulation is the right answer

Bit operations are appropriate for flags, compact sets, hashing, low-level protocols, and subset enumeration — not as a general speed-up.

In those domains the bit representation is the model, so the operations express intent directly rather than encoding arithmetic obscurely.

Bits as the domain model, not as an optimisation.

Use	Appropriate
Permission flags, feature sets	yes - bits are the model
Subset DP over <= 20 elements	yes
Network and file-format fields	yes
Replacing n // 2 with n >> 1	no - the compiler already did it

Interview trap. Rewriting ordinary arithmetic in bit operations reduces readability without improving generated code.

Engineering practice. Ask whether bits are the domain model; if they are not, write the arithmetic.