Day 3 — Number Bases & Binary Arithmetic

Updated

July 30, 2025

Day 3 — Number Bases & Binary Arithmetic

Day 6 — Positional bases

Stage I · concept day
Goal: Interpret place-value polynomials in any base \(b\ge 2\); convert among bases \(2\)–\(16\); map hex↔︎binary by nibbles; validate digits; evaluate with Horner’s method.

Why this matters

Computers are binary; humans often debug in hex. Network addresses, color codes, bitmasks, and file offsets are base-fluent tasks. Place value is the same idea as decimal—only the radix changes.

Theory

Place-value polynomial

Fix an integer base (radix) \(b\ge 2\). Digits \(d_i\) satisfy \(0\le d_i<b\). A finite representation

\[(d_n d_{n-1}\ldots d_1 d_0)_b\]

means the integer

\[N=\sum_{i=0}^{n} d_i\, b^{i}=d_n b^{n}+d_{n-1}b^{n-1}+\cdots+d_1 b+d_0.\]

Examples: \((1011)_2=8+2+1=11_{10}\).
\((2A)_{16}=2\cdot 16+10=42_{10}\).

Fractional part \((0.d_{-1}d_{-2}\ldots)_b=\sum_{k\ge 1}d_{-k}b^{-k}\) exists but we focus on integers unless needed.

Digit symbols for bases up to \(16\)

Value Symbol
\(0\)–\(9\) 0–9
\(10\) A (or a)
\(11\) B
\(12\) C
\(13\) D
\(14\) E
\(15\) F

Digit validity: in base \(b\), every digit must be in \(\{0,1,\ldots,b-1\}\).
\((2A)_{16}\) OK; \((2A)_8\) invalid (A is not a digit in base \(8\)).
\((18)_8\) invalid because digit \(8\not< 8\).

Horner’s method (evaluation)

Rewrite \[N=d_0+b(d_1+b(d_2+b(\cdots+b d_n)\cdots)).\]

Algorithm: start acc = 0; for digits from most significant to least: acc = acc * b + next_digit.

Horner minimizes multiplications and is how parseInt style conversions often work. Same idea as polynomial evaluation (Day 15).

Conversion: base \(b\) → decimal

Expand place values or run Horner with base \(b\).

Conversion: decimal → base \(b\)

Repeated division: while \(N>0\): remainder \(N\bmod b\) is the next least significant digit; replace \(N\leftarrow\lfloor N/b\rfloor\). Then reverse remainders to write MSD-first.

Example: \(42\) to binary:
\(42=2\cdot 21+0\), \(21=2\cdot 10+1\), \(10=2\cdot 5+0\), \(5=2\cdot 2+1\), \(2=2\cdot 1+0\), \(1=2\cdot 0+1\).
Remainders LSB→MSB: \(0,1,0,1,0,1\) → reverse → \((101010)_2\).

Binary ↔︎ hexadecimal (nibble map)

One hex digit \(=4\) bits (a nibble), because \(16=2^4\).

Hex Binary Hex Binary
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111

Binary → hex: pad left to multiple of \(4\) bits; replace each group.
Hex → binary: replace each hex digit by its \(4\)-bit pattern.

Binary ↔︎ octal: groups of \(3\) bits (\(8=2^3\)).

Conversion between arbitrary bases

Common path: base \(b_1\) → decimal → base \(b_2\).
Or: if both powers of two, regroup bits (bin/oct/hex).

Range of \(k\)-digit strings

In base \(b\), \(k\)-digit strings (allowing leading zeros) represent \(0,1,\ldots,b^k-1\) — exactly \(b^k\) values.
Without leading zeros, largest \(k\)-digit number is \(b^k-1\).

Worked examples

Example 1 — Expand binary

\((110101)_2=32+16+4+1=53_{10}\).

Example 2 — Horner binary

Digits \(1,1,0,1,0,1\):
\(0\cdot 2+1=1\)
\(1\cdot 2+1=3\)
\(3\cdot 2+0=6\)
\(6\cdot 2+1=13\)
\(13\cdot 2+0=26\)
\(26\cdot 2+1=53\).

Example 3 — Decimal to hex

\(255\) to hex: \(255=15\cdot 16+15\) → digits F,F → (FF)\(_{16}\).
\(256=(100)_{16}\).

Example 4 — Hex to decimal

(C0FFEE)\(_{16}\) is large; smaller: (2F)\(_{16}=2\cdot 16+15=47\).

Example 5 — Nibble convert

\((1010\,1111\,0001)_2\) → group 1010 1111 0001 → A F 1 → (AF1)\(_{16}\).

Example 6 — Hex to binary

(7B)\(_{16}\) → 0111 1011 → \((1111011)_2\) (drop leading zero if desired).

Example 7 — Octal

\((157)_8=1\cdot 64+5\cdot 8+7=111_{10}\).
Binary via 3-bit: \(001\) \(101\) \(111\) → \((1101111)_2\).

Example 8 — Invalid digits

Is \((308)_8\) valid? Digit \(8\) invalid. \((G1)_{16}\) invalid. \((1012)_2\) invalid digit \(2\).

Example 9 — Base \(5\)

\((243)_5=2\cdot 25+4\cdot 5+3=73_{10}\).
Convert \(73\) to base \(5\): \(73=2\cdot 25+23\), \(23=4\cdot 5+3\) → wait systematic:
\(73=14\cdot 5+3\), \(14=2\cdot 5+4\), \(2=0\cdot 5+2\) → \((243)_5\).

Example 10 — Count values

\(8\)-bit strings: \(2^8=256\) values \(0..255\).
\(2\)-digit hex: \(16^2=256\) values — same count as \(8\) bits.

Example 11 — Color

#FF8800 → \(R=(FF)_{16}=255\), \(G=(88)_{16}=136\), \(B=(00)_{16}=0\).

Example 12 — Mixed base chain

\((1A)_{16}\to\) binary 0001 1010 \(\to\) octal groups 00 011 010 \(= (032)_8= (32)_8\).

Example 13 — Horner hex

(3E8)\(_{16}\): digits \(3,14,8\):
\(0\cdot 16+3=3\), \(3\cdot 16+14=62\), \(62\cdot 16+8=1000_{10}\). (Indeed \(1000=3\cdot 256+14\cdot 16+8\).)

Example 14 — Why pad bits

\((1111)_2=(F)_{16}\). Without padding, grouping \((1\,111)\) wrong if you split as \(1\) and \(111\). Always pad MSD side to full nibble.

Exercises

Easy

  1. Convert \((10110)_2\) to decimal.
  2. Convert \(45_{10}\) to binary.
  3. Convert \((2C)_{16}\) to decimal and to binary.
  4. Which are invalid? \((19)_8\), \((19)_{16}\), \((102)_2\), \((AB)_{10}\).
  5. Map BEEF hex to binary (each digit).

Medium

  1. Convert \(1000_{10}\) to hex using repeated division.
  2. Convert \((345)_6\) to decimal; then to base \(4\).
  3. Evaluate \((11011101)_2\) by Horner; check by place values.
  4. Convert \((777)_8\) to binary and hex.
  5. How many distinct values do \(k\)-digit base-\(b\) strings (leading zeros allowed) represent?
  6. Write \(2^{10}-1\) in binary and hex.
  7. Convert \((0.1)_2\) to a decimal fraction (optional fractional practice).
  8. Express \(255\) and \(256\) in binary, octal, and hex.

Hard

  1. Prove that the repeated-division algorithm yields correct digits (uniqueness of base-\(b\) expansion for \(N\ge 0\)).
  2. Show every nonnegative integer has a unique representation in base \(b\) without leading zeros (except \(0\) itself).
  3. Convert \((1A3)_{16}\) to base \(7\) (via decimal).
  4. Explain why binary↔︎hex needs groups of \(4\), not \(3\).
  5. What is the largest \(4\)-digit number in base \(b\)? In decimal?
  6. Horner: count multiplications to evaluate an \(n\)-digit base-\(b\) numeral vs naive powers.
  7. Show \((d_n\ldots d_0)_b < b^{n+1}\).

Challenge / CS-flavored

  1. IPv4 address bytes as decimal vs hex dump: \(192.168.0.1\) — write each octet in hex.
  2. Bitmask 0xF0 in binary; which bit positions (0-based from LSB) are set?
  3. Parse algorithm: implement Horner by hand for string "1F" base \(16\).
  4. Why do programmers prefer hex over decimal for \(32\)-bit patterns?
  5. Base \(64\) uses \(64\) symbols (not computed in detail): how many bits per digit conceptually?

Uniqueness of representation

Theorem. Fix base \(b\ge 2\). Every integer \(N\ge 0\) has a unique sequence of digits \(0\le d_i<b\) with \(d_n\neq 0\) if \(N>0\) such that \(N=\sum_{i=0}^{n} d_i b^{i}\).

Proof sketch. Existence by repeated division. Uniqueness: if two expansions equal, subtract; smallest differing digit would imply \(b\) divides a digit difference with absolute value \(<b\), forcing difference \(0\). \(\square\)

Fractional bases (brief)

\((0.d_{-1}d_{-2}\ldots d_{-m})_b=\sum_{k=1}^{m} d_{-k} b^{-k}\).
Binary fractions: \((0.11)_2=\frac{1}{2}+\frac{1}{4}=\frac{3}{4}\).
Terminating in base \(b\) relates to denominators dividing a power of \(b\) (Day 3 analogue).

Mixed-radix note

Time (hours/minutes/seconds) is mixed radix \(24\)–\(60\)–\(60\), not pure base—but place-value thinking still applies with varying weights.

Horner complexity

Degree-\(n\) (or \(n+1\) digits): \(n\) multiplications by \(b\) and \(n\) additions. Naive \(\sum d_i b^i\) with fresh powers can use more multiplies unless powers are cached.

Conversion drills (worked)

Drill. \(1000_{10}\) to binary: repeated \(\div 2\) → \((1111101000)_2\). Hex: \(1000=3\cdot 256+232\), \(232=14\cdot 16+8\) → (3E8)\(_{16}\).
Drill. (DEAD)\(_{16}\) → binary nibble string 1101 1110 1010 1101.
Drill. Invalid: (2G)\(_{16}\), (18)_8, (210)_2.

Extra exercises

  1. Prove uniqueness of base-\(b\) digits for \(N\ge 0\) (write the difference argument carefully).
  2. Convert \((0.001)_2\) and \((0.1)_{16}\) to decimal fractions.
  3. Express \(2^{16}-1\) in hex and binary.
  4. How many hex digits are needed for all \(32\)-bit patterns (including leading zeros as fixed width)?
  5. Parse "FF" with Horner in base \(16\) step by step; repeat in base \(15\) with digit values—why base \(15\) digit F is invalid.

CS connection

Memory dumps, HTML colors, Unicode code points (U+1F600), machine code, and MAC addresses are hex-heavy. Binary is the hardware truth; octal still appears in Unix file modes (0755). Horner’s method is polynomial evaluation—same as efficient x^n accumulation patterns. Validating digits is input sanitation for parsers.

Common pitfalls

Pitfall What to do instead
Reading hex as decimal Expand powers of \(16\)
Wrong nibble grouping Pad to multiples of \(4\) from the left
Invalid digits Enforce \(0\le d<b\)
Remainder order reversed LSB is first remainder; reverse for writing
Assuming unique length Leading zeros do not change value
Base \(b\) digit $b$ Digits only to \(b-1\)

End-of-day synthesis problems

S1. Convert \(365_{10}\) to binary, octal, and hex.

S2. Horner-evaluate (BEEF)\(_{16}\) to decimal (you may compute stepwise).

S3. Convert (1011 1100 0001 1111)_2 to hex by nibbles.

S4. Which are valid? (1A)_12, (1A)_10, (70)_8, (70)_7.

S5. Prove every \(N\) with \(0\le N<b^{k}\) has a unique \(k\)-digit base-\(b\) representation allowing leading zeros.

S6. Explain why \(16^{2}=256=2^{8}\) means two hex digits match one byte.

S7. Convert \((144)_{5}\) to base \(3\) via decimal.

S8. Color #C0FFEE: write RGB decimal triples.

Checkpoint

  • Expand any base-\(b\) numeral via \(\sum d_i b^i\)
  • Convert decimal \(\leftrightarrow\) base \(b\) by division/Horner
  • Convert binary \(\leftrightarrow\) hex by nibbles fluently
  • Detect invalid digit strings
  • State how many values \(k\) digits in base \(b\) encode
  • Finish S1–S4 timed (15 minutes)

Write two takeaways in your own words.

Deep dive — place value, Horner, nibble fluency

D1 — Repeated division to hex (worked fully).
Convert \(365_{10}\) to hex:
\(365=22\cdot 16+13\),
\(22=1\cdot 16+6\),
\(1=0\cdot 16+1\).
Digits LSB-first \(13,6,1\) → reverse → (16D)\(_{16}\).
Check: \(1\cdot 256+6\cdot 16+13=256+96+13=365\).

D2 — Binary to hex with padding discipline.
\((11011110101)_2\): pad left to multiple of \(4\): \(0110\,1111\,0101\) → 6 F 5 → (6F5)\(_{16}\).
Mis-grouping from the right without padding the left is the classic error when bit length \(\not\equiv 0\pmod 4\).

D3 — Horner in base \(7\).
\((254)_7\): \(0\cdot 7+2=2\), \(2\cdot 7+5=19\), \(19\cdot 7+4=137_{10}\).
Place values: \(2\cdot 49+5\cdot 7+4=98+35+4=137\).

D4 — Arbitrary base path.
\((144)_5\to\) decimal \(1\cdot 25+4\cdot 5+4=49\), then \(49\) to base \(3\):
\(49=16\cdot 3+1\), \(16=5\cdot 3+1\), \(5=1\cdot 3+2\), \(1=0\cdot 3+1\) → \((1211)_3\).

D5 — Range counts that match bit widths.
\(12\)-bit unsigned: \(2^{12}=4096\) values.
\(3\) hex digits: \(16^3=4096\) — same cardinality; fixed-width hex dump of a \(12\)-bit field uses \(3\) digits (sometimes written with a leading nibble share in \(16\)-bit words).

D6 — Invalid digit detection algorithm (mental).
Scan each character; map 0–9,A–F to values; reject if value \(\ge b\).
(2G)\(_{16}\) fails on G; (70)_7 fails on digit 7; (102)_2 fails on 2.

Extra practice set

  1. Convert \(1000_{10}\) to binary, octal, and hex; verify hex via nibbles from binary.
  2. Horner-evaluate (C0DE)\(_{16}\) to decimal (stepwise accumulation).
  3. Convert (775)_8 to binary by \(3\)-bit groups, then to hex by \(4\)-bit groups.
  4. Prove uniqueness sketch: if two base-\(b\) expansions of \(N\) differ, derive a contradiction from digit bounds.
  5. How many distinct values do \(4\)-digit base-\(5\) strings represent (leading zeros allowed)?

Tomorrow

Day 7 — Binary arithmetic & two’s complement. Add/sub, \(n\)-bit two’s complement range, overflow, bitwise ops as integer ideas, shifts as \(\times 2\) / \(\div 2\).

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.