Bit manipulation you can do by hand

Bit questions are short, and interviewers often slow them down on purpose: "What is that in binary? What does this shift give for a negative number?" Candidates who can work the bits on paper tend to write the code right the first time, and candidates who memorized one-liners stall when the numbers change. After this page you can add and multiply in base 2 by hand, write a negative number in two's complement, make Python behave like a 32-bit integer, and build masks that read and write single bits or hold a small set.

Adding and multiplying on paper

Each binary digit (bit) is worth twice the one to its right: 1, 2, 4, 8, 16 and so on, starting from the right. 45 is 32 + 8 + 4 + 1, so it is 101101. "Bit i" means the bit worth 2^i, counting from 0 at the right.

Addition works like decimal addition with one rule: 1 + 1 is 10, so write 0 and carry 1, and 1 + 1 plus a carry is 11, so write 1 and carry 1. Here is 45 + 27:

The answer, 1001000, is 64 + 8 = 72.

Multiplication is easier than in decimal, because each digit of the multiplier is 0 or 1: for each digit you either copy the other number, shifted, or write nothing. For 13 × 6, that is 1101 × 110:

The table also shows what shifts mean: x << k multiplies x by 2^k, and x >> k drops the low k bits, which divides by 2^k and rounds down.

The operators, one column at a time

Bitwise operators work on each column separately, with no carries. Python spells them & (AND), | (OR), ^ (XOR, exclusive or) and ~ (NOT), plus the shifts << and >>.

NOT takes one number and turns every 0 into 1 and every 1 into 0. Read the other columns as jobs: AND with a mask keeps the bits where the mask has 1s and clears the rest, OR turns the mask's bits on, XOR toggles them. Here one mask, 00001111 (the low four bits, written (1 << 4) - 1), meets 10110100 three ways:

When an interviewer asks what an expression does, work a line like this on paper. It takes thirty seconds and ends the guessing.

Negative numbers in two's complement

Fixed-width integers store negatives in two's complement: in w bits, the top bit is worth -2^(w-1) instead of +2^(w-1), and the others keep their usual values. In 8 bits the top bit is worth -128, so the range is -128 to 127. To write -20, write 20, invert every bit, then add 1:

Check it with place values: -128 + 64 + 32 + 8 + 4 = -20. Hardware uses this form because ordinary addition just works: 00010100 + 11101100 is 1 00000000, and dropping the carry off the top leaves 0, which is 20 + (-20).

Two more patterns to know. -1 is all 1s (11111111). The most negative value, 10000000 (-128), has no positive partner, so negating it overflows back to itself; in 32 bits, that is why Java's Math.abs(Integer.MIN_VALUE) returns a negative number.

Python's bin(-20) prints -0b10100, a minus sign and the magnitude, not the stored bits. To see the 8-bit pattern, use format(-20 & 0xFF, "08b").

Shifts, widths and Python's unbounded integers

A left shift fills with zeros. A right shift comes in two kinds. An arithmetic shift copies the sign bit into the vacated places, so negatives stay negative: shifting 11101100 (-20) right by 2 gives 11111011, which is -5. A logical shift fills with zeros instead: the same bits become 00111011, which is 59. Java and JavaScript write them >> and >>>; in C and C++ the type decides, and unsigned values shift logically.

Python has only the arithmetic kind, and its integers have no fixed width: a negative int behaves as if it had infinitely many 1s on the left, and nothing overflows. Every arithmetic right shift rounds toward minus infinity, so -21 >> 2 is -6 in Python and Java alike. Python's -21 // 4 agrees, but Java's and C's -21 / 4 truncate to -5, so there x >> k and x / 2^k differ for a negative x that 2^k doesn't divide. When a prompt says "32-bit integer", impose the width yourself with a mask:

MASK32 = 0xFFFFFFFF

def to_u32(x):
    """The low 32 bits of x, read as an unsigned number."""
    return x & MASK32

def to_i32(x):
    """The low 32 bits of x, read as a signed (two's complement) number."""
    x &= MASK32
    return x - (1 << 32) if x & (1 << 31) else x

def logical_right_shift(x, k):
    """What Java's x >>> k gives for a 32-bit int x."""
    return to_u32(x) >> k

to_i32(2**31 - 1 + 1) wraps to -2,147,483,648, just as Java's Integer.MAX_VALUE + 1 does.

"Python integers don't overflow, so I'll AND with 0xFFFFFFFF after each step to stay in 32 bits, and convert back to signed at the end."

The mistake interviewers watch for is a loop like while x: ...; x >>= 1 that walks the bits of x. For a negative x in Python it never ends, because -1 >> 1 is still -1. The interviewer sees your code hang on the first negative test. Mask first with x = to_u32(x) and the loop stops within 32 steps.

Reading and writing one bit

To touch bit i, build a mask with a single 1 in place i, 1 << i, and pick the operator from the truth table. Here a recurring meeting stores its days in one int, bit 0 for Monday through bit 6 for Sunday:

MON, TUE, WED, THU, FRI, SAT, SUN = range(7)

def has_day(days, d):
    return bool(days & (1 << d))

def add_day(days, d):
    return days | (1 << d)

def drop_day(days, d):
    return days & ~(1 << d)

def set_day(days, d, on):
    """Force bit d to 1 if on is true, else to 0."""
    return drop_day(days, d) | (int(on) << d)

def toggle_day(days, d):
    return days ^ (1 << d)

set_day clears the bit and then ORs in the new value, so it works whichever way the bit started. ~(1 << d) is negative in Python (~8 is -9), which is fine: ANDing it with a non-negative days keeps only real bits.

The bug here is days & (1 << d) == 1. When the bit is set, the AND gives 2^d, not 1, so the test fails for every day but Monday. The interviewer sees Thursday reported free when it is booked. Compare with != 0, or use bool() as has_day does. In C and Java, != binds tighter than &, so write (x & mask) != 0 with the parentheses.

XOR pairs and small sets

XOR cancels matching pairs

The XOR column gives three facts: x ^ x is 0, x ^ 0 is x, and the order of XORs doesn't matter. XOR a whole list together and every value that appears twice cancels, leaving whatever appears an odd number of times. Say every order ID shows up twice in a log, once when placed and once when shipped, except one order that never shipped:

def unshipped(order_ids):
    """Every ID is logged twice (placed, shipped) except one that never shipped."""
    leftover = 0
    for order_id in order_ids:
        leftover ^= order_id
    return leftover

That is O(n) time for n log lines and O(1) space, against O(n) space for a counting dict. State its limits before you rely on it: exactly one ID may be unmatched, the others must appear an even number of times (with one ID appearing three times, 4 ^ 4 ^ 4 ^ 9 gives 13, not 9), and an unmatched ID of 0 looks the same as no unmatched ID.

A small set in one integer

With n items, one int can hold any subset: bit i is 1 when item i is in. If items are skills, then:

• union is a | b, intersection a & b, and difference a & ~b;

• (alice | bob) & need == need asks whether the pair covers every skill in need;

• a.bit_count() is the set's size (Python 3.10 and later).

To visit only the subsets of one mask, for example every way to divide the skills in need between two people:

def subsets(mask):
    """Every subset of mask, largest first, ending with the empty set 0."""
    sub = mask
    while True:
        yield sub
        if sub == 0:
            return
        sub = (sub - 1) & mask

def two_way_splits(need):
    """Each way to divide the skills in need between two people."""
    return [(part, need ^ part) for part in subsets(need)]

(sub - 1) & mask is the largest subset of mask below sub, so the loop walks every subset in decreasing order and stops after the empty one. A mask with k members has 2^k subsets. Looping over the subsets of every mask of n bits costs 3^n in total, since each item is outside the mask, inside it but outside the subset, or in both. A mask also makes a compact key for a memoized state, which From recursion to dynamic programming puts to use.

Practicing with these questions

Do each card on paper before you code it. Pick a small input, write it in binary at a fixed width (8 bits is usually enough), and work the operations column by column. Write down the output your hand trace gives, then code and compare. If the prompt names a width, such as 32 bits or a 64-bit word, say out loud how you will enforce it in Python before the first line.

Implement streaming RLE and bit-packed codec is the longest of these, so do it last, once the width habit is automatic. For short daily reps, the Blind 75 bit manipulation problems fit the same routine.