Day 7 — Binary arithmetic & two’s complement

Updated

July 30, 2026

Day 7 — Binary arithmetic & two’s complement

Stage I · concept day
Goal: Add and subtract binary integers; master \(n\)-bit two’s complement range \(-2^{n-1}..2^{n-1}-1\); detect overflow; interpret bitwise AND/OR/XOR as integer operations; relate shifts to \(\times 2\) and \(\div 2\).

Why this matters

Fixed-width integers wrap; security bugs and game-score glitches are often overflow. Two’s complement is the universal signed representation in modern CPUs. Bitwise ops implement flags, masks, and set operations on bitsets.

Theory

Unsigned binary addition

Add bit by bit with carry, same as decimal.

  1 1 1      carries
    0 1 0 1
  + 0 1 1 1
  ---------
    1 1 0 0

\(5+7=12\). In fixed width \(n\), discard carry out of the top bit for modular arithmetic \(\mathrm{mod}\,2^n\).

Unsigned range

\(n\)-bit unsigned values: \(0,1,\ldots,2^n-1\).
Addition overflow (unsigned): sum \(\ge 2^n\) (carry out of MSB).

Two’s complement representation

For width \(n\), bit patterns still \(0..2^n-1\) as unsigned, but interpreted signed:

  • If MSB (sign bit) is \(0\): value is the usual nonnegative integer \(0..2^{n-1}-1\).
  • If MSB is \(1\): value is \(-(2^n - U)\) where \(U\) is the unsigned interpretation, equivalently \(U-2^n\).

Range: \[-2^{n-1},\; -2^{n-1}+1,\; \ldots,\; -1,\; 0,\; 1,\; \ldots,\; 2^{n-1}-1.\]

Note the asymmetry: one more negative value than positive; \(-2^{n-1}\) has no positive counterpart in-range.

Examples (\(n=8\)): range \(-128..127\).
00000000 \(=0\), 01111111 \(=127\), 10000000 \(=-128\), 11111111 \(=-1\).

Negation in two’s complement

To compute \(-x\) when \(x\) is in range and \(-x\) is representable:

  1. Invert all bits (ones’ complement).
  2. Add \(1\).

Why (sketch): bit invert of \(x\) is \((2^n-1)-x\); add \(1\) gives \(2^n-x\), which \(\mathrm{mod}\,2^n\) is the representative of \(-x\).

Special case: negating \(-2^{n-1}\) overflows (no positive \(2^{n-1}\) in \(n\) bits).

Two’s complement addition / subtraction

Add bit patterns as unsigned; interpret the result as two’s complement.
Subtraction: \(a-b=a+(-b)\) with two’s complement negation of \(b\).

Overflow detection (signed)

For two’s complement addition of \(a\) and \(b\):

  • Overflow can occur when \(a\) and \(b\) have the same sign.
  • Classic rule: overflow iff carry into MSB differs from carry out of MSB.
  • Or: result sign is wrong (two positives sum negative, or two negatives sum positive).

Unsigned overflow \(\neq\) signed overflow for the same bit add.

Bitwise operations (integer idea)

Treat integers as bit vectors (usually two’s complement / unsigned bits).

Op Bit rule Integer intuition
AND & \(1\) iff both \(1\) mask bits; intersection of set bits
OR \| \(1\) if either \(1\) set bits; union
XOR ^ \(1\) if bits differ toggle; symmetric difference
NOT ~ flip each bit ones’ complement; in \(n\) bits, \(~x = (2^n-1)-x\)

Examples: \(x\;\&\;1\) is \(0\) or \(1\) by parity of LSB.
\(x\;\|\;(1\ll k)\) sets bit \(k\).
\(x\;\&\;\sim(1\ll k)\) clears bit \(k\) (in infinite or wide enough width carefully).

Shifts

Logical left shift \(x\ll k\) (within infinite precision): multiplies by \(2^k\) if no overflow.
Logical right shift on nonnegative: \(\lfloor x/2^k\rfloor\).
Arithmetic right shift on signed two’s complement: shifts in copies of the sign bit (approximates floor division by \(2^k\) for negatives in many ISAs).

In fixed width, left shift discards bits that leave the register (overflow / wrap).

Worked examples

Example 1 — Binary add

\(13+11\): \((1101)_2+(1011)_2=(11000)_2=24\). Check \(13+11=24\).

Example 2 — 4-bit unsigned wrap

\(4\)-bit: \(12+7=19\equiv 3\pmod{16}\) → bits 0011 if only \(4\) bits kept. Carry out \(=1\).

Example 3 — 8-bit two’s complement of \(-5\)

\(5=(00000101)_2\), invert 11111010, add \(1\) → 11111011.
Unsigned value \(251\); \(251-256=-5\). ✓

Example 4 — Negate \(-1\)

\(8\)-bit -1 = 11111111. Invert 00000000, add \(1\) → 00000001 \(=+1\).

Example 5 — Add signed \(8\)-bit

\(50+100=150\) not in \(-128..127\): overflow.
\(50=(00110010)_2\), \(100=(01100100)_2\), sum 10010110 which as signed is negative (MSB \(1\)) → overflow detected.

Example 6 — Successful signed add

\(-5+3\): 11111011 + 00000011 = 11111110 \(=-2\). Correct, no overflow.

Example 7 — Subtract via add

\(7-5=7+(-5)\): 00000111 + 11111011 = 00000010 \(=2\) (8-bit).

Example 8 — Range extremes

\(n=5\): range \(-16..15\). Pattern 10000 \(=-16\); 01111 \(=15\); 11111 $=-1`.

Example 9 — Bitwise AND/OR/XOR

\(x=13=(1101)_2\), \(y=11=(1011)_2\).
AND 1001 \(=9\), OR 1111 \(=15\), XOR 0110 \(=6\).
Check \(9+6=15\) and \(13+11=24\neq\) that identity—use bit meaning not decimal add.

Example 10 — Mask

Extract low \(4\) bits: \(x\;\&\; 0xF\). For \(x=0x5A3\), result \(0x3\).

Example 11 — Left shift

\(5\ll 2=20\) if enough bits. Binary 101 → 10100.

Example 12 — Right shift nonnegative

\(20\gg 2=5\). 10100 → 101.

Example 13 — Why \(-128\) is special (\(n=8\))

10000000 invert 01111111 add \(1\) → 10000000 again: negation fails / same pattern; \(128\) not representable.

Example 14 — Flags

Permission bits: read \(=4\), write \(=2\), exec \(=1\) (Unix-ish). Mode \(7=\) rwx via OR of flags; test write with mode & 2.

Exercises

Easy

  1. Add \((1011)_2+(0110)_2\); convert sum to decimal.
  2. Write \(8\)-bit two’s complement for \(19\) and for \(-19\).
  3. What is the range for \(n=6\) two’s complement?
  4. Compute \(13\;\&\;7\), \(13\| 7\), \(13\hat{}7\) in decimal and binary.
  5. Compute \(9\ll 1\) and \(9\gg 1\).

Medium

  1. Show step-by-step two’s complement negation of \(42\) in \(8\) bits; verify by unsigned \(U-256\).
  2. Add \(8\)-bit patterns for \(-10\) and \(-20\); interpret result; overflow?
  3. Add \(100+50\) in \(8\)-bit two’s complement; detect overflow.
  4. Prove that 111...1 (\(n\) ones) represents \(-1\) in two’s complement.
  5. Convert \(-1\), \(-2\), \(-128\) to \(8\)-bit patterns.
  6. Using masks, clear the lowest set bit idea: \(x\;\&\;(x-1)\) — try \(x=12\) and \(x=8\).
  7. Explain unsigned vs signed overflow for bit-add of 1111 + 0001 in \(4\) bits.
  8. What is \(\sim 0\) in \(8\)-bit pure flip? As signed two’s complement value?

Hard

  1. Prove: if \(0\le x<2^{n-1}\), the two’s complement of \(-x\) is \(2^n-x\) as an \(n\)-bit string.
  2. Show the representable set has \(2^n\) values and covers exactly \(-2^{n-1}..2^{n-1}-1\).
  3. Argue why same-sign addition is the overflow danger case (with examples).
  4. Verify \(a+b = (a\hat{}b) + 2(a\& b)\) for nonnegative \(a,b\) small enough (identity relating XOR/AND).
  5. Arithmetic vs logical right shift of 11110000 as \(8\)-bit: describe both results.
  6. Can every integer in range be negated except one? Which?
  7. Design a \(4\)-bit example where unsigned addition has carry-out but signed interpretation has no overflow (or vice versa).

Challenge / CS-flavored

  1. Game score stored in \(8\)-bit signed: \(120+20\) → ? What displays?
  2. Alignment: address \(a\), align to \(8\) bytes: \((a+7)\;\&\;\sim 7\) idea—compute for \(a=13\) with \(8\)-bit toy masks carefully.
  3. Why is two’s complement preferred over sign-magnitude for hardware addition?
  4. Bitset: union/intersection as OR/AND for sets \(\{0,2,3\}\) and \(\{1,2\}\) as \(4\)-bit masks.
  5. Shift: show \(x\ll k = x\cdot 2^k\) for \(x=7\), \(k=3\) with enough bit width.

Sign-magnitude and ones’ complement (contrast)

Sign-magnitude: MSB is sign, remaining bits magnitude. Two zeros (\(+0,-0\)). Addition needs separate sign logic.
Ones’ complement: negate by bit flip only; also dual zeros. End-around carry historically.
Two’s complement: single zero, addition hardware unified—why it won.

Overflow vs carry

  • Carry flag (unsigned): carry out of MSB.
  • Overflow flag (signed): result not representable in signed range—often XOR of carry-in and carry-out of sign bit.
    Same bit addition can set one flag and not the other.

Bit identities (useful)

  • \(x\;\&\; x = x\), \(x\| x=x\), \(x\hat{}x=0\)
  • \(x\;\&\; 0=0\), \(x\| 0=x\), \(x\hat{}0=x\)
  • De Morgan bit form: \(\sim(x\& y)=(\sim x)\|(\sim y)\) in infinite width / defined width carefully
  • \(x\;\&\;(x-1)\) clears lowest set bit (for \(x\neq 0\))

Arithmetic right shift (signed)

For negative two’s complement, shifting right while filling with \(1\)s approximates \(\lfloor x/2\rfloor\). Example \(8\)-bit \(-8=(11111000)_2\); arithmetic \(\gg 1\) → \((11111100)_2=-4\).

Extra worked overflow matrix (\(4\)-bit)

Range \(-8..7\). Compute \(5+4=9\) not representable → overflow. \(-5+-4=-9\) not representable → overflow. \(5+(-4)=1\) OK. \(7+1\) overflows to \(-8\) bit pattern 1000.

Extra exercises

  1. Prove that \(n\)-bit two’s complement addition implements addition modulo \(2^n\) on the representatives.
  2. Show there are exactly \(2^{n-1}\) negative values and \(2^{n-1}\) nonnegative values in \(n\)-bit two’s complement (including \(0\)).
  3. Implement \(x-y\) as \(x+\sim y+1\) on paper for \(x=13\), \(y=5\) in \(8\) bits.
  4. Which \(8\)-bit patterns are negative? Give a bit test.
  5. Explain why INT_MIN == -INT_MIN can hold in two’s complement width (when negation overflows).

CS connection

CPUs ALUs add two’s complement natively. Languages expose + with wrap (unsigned) or undefined/panic/checked options for overflow. Bitwise ops drive flags, bloom filters (idea), compression codes, and graphics masks. Shifts optimize \(\times 2^k\) in integer code when overflow is impossible or intentional \(\mathrm{mod}\,2^n\).

Common pitfalls

Pitfall What to do instead
Thinking signed range is \(\pm 2^{n-1}\) Max positive is \(2^{n-1}-1\)
Sign-magnitude addition rules Two’s complement uses ordinary binary add
Ignoring overflow Check same-sign / carry rules
Logical right shift on negatives Arithmetic shift if you need floor-div behavior
Confusing NOT with negate Negate = invert + 1
Assuming \(-x\) always representable \(-2^{n-1}\) is the trap

End-of-day synthesis problems

S1. Add \(8\)-bit patterns for \(100\) and \(40\) as unsigned and as signed; discuss overflow each way.

S2. Give \(8\)-bit two’s complement encodings of \(0,1,-1,127,-128,-20\).

S3. Prove invert-plus-one yields \(-x\) mod \(2^{n}\) when defined.

S4. Compute \(0b1100 \;\&\; 0b1010\), OR, XOR; interpret as set ops on bit indices \(\{2,3\}\) and \(\{1,3\}\).

S5. Show \(x\ll 3 = 8x\) for \(x=9\) with enough width; what happens in \(8\)-bit if \(x=40\)?

S6. Why is there no \(8\)-bit two’s complement of \(+128\)?

S7. Detect overflow for \(60+70\) in \(8\)-bit signed by sign-bit reasoning.

S8. Express subtraction \(25-30\) as addition of two’s complement \(-30\) in \(8\) bits; verify result \(-5\).

Checkpoint

  • Add binary numbers with carries
  • State \(n\)-bit two’s complement range
  • Negate by invert-plus-one; know the exceptional min value
  • Detect a signed overflow example
  • Compute AND/OR/XOR and simple masks
  • Relate \(\ll 1\) to \(\times 2\) and \(\gg 1\) to \(\lfloor/2\rfloor\) for nonnegative
  • Complete S2 and S6 from memory

Write two takeaways in your own words.

Deep dive — two’s complement, overflow, bitwise

D1 — Encode a gallery of \(8\)-bit values.
| Value | Pattern | Notes | |——:|:——-:|——-| | \(0\) | 00000000 | unique zero | | \(1\) | 00000001 | | | \(-1\) | 11111111 | all bits set | | \(127\) | 01111111 | max positive | | \(-128\) | 10000000 | min; negation trap | | \(-20\) | 11101100 | invert 00010100 → 11101011 +1 |

D2 — Overflow vs carry on the same add.
\(4\)-bit: 1111+0001 = 0000 with carry-out \(1\).
Unsigned: overflow (wrap), result \(0\).
Signed: 1111 \(=-1\), 0001 \(=+1\), sum \(0\) — no signed overflow. Carry and overflow flags diverge.

D3 — Subtraction as addition.
\(25-30\) in \(8\) bits: \(25=(00011001)_2\), \(-30\): start \(30=(00011110)_2\), invert 11100001, +1 → 11100010.
Sum: 00011001+11100010=11111011 \(=-5\). Check \(25-30=-5\).

D4 — Bitset union/intersection.
Set \(A=\{0,2,3\}\) as mask bits 1101 (value \(13\) if bit \(0\) is LSB).
Set \(B=\{1,2\}\) as 0110 (value \(6\)).
Union OR 1111 \(=15\); intersection AND 0100 \(=4\) (only element \(2\)).

D5 — Shift identities with width caution.
\(x=9\), \(k=3\): \(9\ll 3=72=9\cdot 8\) in unlimited width.
In \(8\)-bit, \(x=40=(00101000)_2\), \(40\ll 3\) shifts out high bits → not \(320\); modular left shift discards.

D6 — Why two’s complement won (hardware narrative).
Sign-magnitude needs separate adder paths for signs; ones’ complement has dual zeros and end-around carry. Two’s complement: one zero, same adder for signed and unsigned bit patterns, subtraction via invert-plus-one cheaply.

Extra practice set

  1. Write \(n=6\) two’s complement range; encode \(-1\), \(-32\), \(15\).
  2. Add \(8\)-bit \(60+70\); detect signed overflow by sign-bit rule.
  3. Prove 11…1 (\(n\) ones) is \(-1\) because unsigned \(2^n-1\) maps to \((2^n-1)-2^n=-1\).
  4. Compute \(0b101101 \& 0b011010\), OR, XOR.
  5. Explain INT_MIN == -INT_MIN in \(n\)-bit two’s complement (negation of min fails).

Tomorrow

Day 8 — Exponents & logarithms. Integer exponent laws with proofs, roots, log definitions, change of base, \(\log_2\) and bits/information, simple exponential equations.