Lesson 16 of 16 · 17:23
Binary & bit manipulation
Bits are simply binary digits with positional value. Bit manipulation becomes approachable when you stop treating expressions as tricks and instead write the relevant bits, the mask, and the truth-table operation. Fixed width and signed representation explain the cases that otherwise feel surprising.
Interview bit problems usually use a mask to test, set, clear, or toggle positions, or use XOR cancellation to summarize paired values. Always state the integer-width and sign assumptions when shifts or complements are involved.
What you should be able to do after this lesson
- Read binary by powers of two
- Derive masks instead of memorizing magic numbers
- Check width and signed-shift behavior
The mental model
An integer is a row of bits with positional weights. Bitwise operations transform every aligned bit pair independently; shifts move those weights.
Recognize it when: Use bits when values encode flags, parity, subsets, powers of two, compact state, unique-number cancellation, or low-level masks and fields.
The invariant to say aloud: Every mask has a named meaning, and each operation changes only the bits claimed by that meaning while preserving the others.
Learn the ideas one at a time
Concept 1 of 6
Bases and binary
Watch from 0:00 ↗Binary uses powers of two. Convert decimal by decomposing into powers or repeated division; read a bit string by summing bit × 2^position.
Each binary position represents a power of two, just as each decimal position represents a power of ten. Converting to decimal sums the active powers. Converting from decimal repeatedly removes or divides by powers of two.
Walk through an example
1101₂ = 1×8 + 1×4 + 0×2 + 1×1 = 13. The rightmost bit is position 0, not position 1.
In an interview
Write position labels over the bits. This prevents off-by-one masks and makes the arithmetic explainable.
Concept 2 of 6
Signed and two’s complement
Watch from 2:15 ↗Fixed-width signed integers reserve the high bit’s interpretation. Two’s complement negation flips bits and adds one, making addition circuitry work for both signs.
In w-bit two's complement, the high bit carries negative weight and values wrap modulo 2^w. Negating flips every bit and adds one. This representation lets the same addition circuitry handle positive and negative values, but a finite width is essential to interpreting NOT and overflow.
Walk through an example
In 8 bits, 5 is 00000101. Flip to 11111010 and add one to get 11111011, the representation of -5.
In an interview
Specify the width when demonstrating negatives. Python integers are unbounded and can display complement behavior differently from fixed-width interview examples.
Concept 3 of 6
Binary arithmetic
Watch from 4:55 ↗Addition carries when a column totals two or more; subtraction borrows. Fixed-width overflow discards carry beyond the available bits.
Binary addition follows decimal addition with base two: 1+1 writes 0 and carries 1; 1+1+1 writes 1 and carries 1. Fixed-width overflow discards a carry beyond the high bit, which is why arithmetic may wrap in some languages.
Walk through an example
0111 + 0001 = 1000 in four bits. Interpreted unsigned, that is 8; interpreted signed two's complement, it crosses from 7 to -8.
In an interview
Separate the bit pattern from its signed or unsigned interpretation. The same bits can represent different numeric values.
Concept 4 of 6
AND / OR / XOR / NOT
Watch from 7:36 ↗AND tests or clears, OR sets, XOR toggles or cancels equal values, and NOT flips. Always reason from a truth table or explicit mask.
AND keeps a bit only when both inputs have it, OR keeps a bit when either has it, XOR keeps differences, and NOT flips within the chosen width. These operations become useful through masks: AND selects or clears, OR sets, and XOR toggles or cancels pairs.
Walk through an example
1010 XOR 0010 = 1000 because only the differing position remains. Also x XOR x = 0 and x XOR 0 = x, which lets equal pairs cancel regardless of order.
In an interview
Show the truth-table effect on the relevant bit. Avoid presenting XOR cancellation as unexplained folklore.
Concept 5 of 6
Shifts
Watch from 11:31 ↗Left shift by k multiplies non-overflowing nonnegative values by 2^k; right shift divides by powers of two with signed-language semantics worth checking.
Left shift moves bits toward higher powers and fills low positions with zero, corresponding to multiplication by 2^k when no relevant overflow occurs. Right shift removes low positions, but negative-value behavior may be arithmetic or logical depending on language and operator.
Walk through an example
0011 << 2 becomes 1100, changing 3 to 12. For nonnegative values, shifting right by one behaves like integer division by two.
In an interview
Mention overflow, sign extension, and language semantics whenever shifts operate on negative or fixed-width values.
Concept 6 of 6
Mask recipes
Watch from 13:34 ↗Test bit k with x & (1<<k), set with OR, clear with AND of an inverted mask, and toggle with XOR.
A one-bit mask is built as 1 << k. Testing uses x & mask; setting uses x | mask; clearing uses x & ~mask within the intended width; toggling uses x ^ mask. Multiple flags are represented by OR-ing their one-bit masks.
Walk through an example
To test bit 3, mask = 00001000. If x & mask is nonzero, the bit is set. To clear it, AND with a mask containing zero at bit 3 and ones elsewhere.
In an interview
Derive the mask from the desired final truth-table behavior and use parentheses around shifts in mixed expressions.
Before you call this lesson done
- Label bit positions
- State width and signedness
- Write the mask explicitly
- Verify the operation on one target bit and one untouched bit
