Binary, Hexadecimal, Two's Complement

I attempted to take a shower between :55 and :05 but ended up joining this Zoom at :11 — not bad. I knew how to do the problems after watching lecture and this Organic Chemistry Tutor video yesterday, but this recitation was incredibly helpful in clarifying some concepts. The TA's really good!

• How do we convert to hexadecimal a bitstring whose length is not a multiple of 4? Since it's unsigned, we add 0s to the left side

• Decimal to hexadecimal: 0-9, 10=A, 11=B, 12=C, 13=D...

  • I was so caught up in binary <> hex that I forgot that decimal <> hex is also a thing
• To sum hex numbers, convert to binary
• Restrictions, overflow, etc. only apply to signed numbers

Two's complement overview

• Different system, as opposed to binary/unsigned
• Most significant bit is negative; if there's a 1 in the most significant bit, we subtract that value (e.g. $-2^4$)
• To negate a number in two's complement: invert all the digits and add 1
• "Normal" subtraction doesn't work in two's complement; instead, invert the second number and add

Range and mod

• N-bit two's complement number: what's the range of values these N bits could represent? $[-2^{N-1}, 2^{N-1}-1]$
• Most negative: e.g. $N=4$: Leftmost bit is $-2^3$, so most negative number we can represent is $-2^3$, or $-2^{N-1}$

• Most positive will look like $0111...111$: $2^0 + 2^1 + ... + 2^{N-2}$ = sum of geometric series = $2^{N-1} - 1$

  • Holy shit I did not realize this was a geometric sum
• How many numbers are in this range: Subtract ends of range and add 1: $2^N$
• Two's complement is modular. Regular mod: N bits can represent $[0, 2^N - 1]$. Here it's shifted over, but the range is the same size: $[-2^{N-1}, 2^{N-1} - 1]$

Overflows with two's complement operations

• Pos + neg: inside range, because most significant bits are 0 and 1
• Pos + pos: sometimes in range
• Neg + neg: sometimes in range
• We drop overflow because two's complement can only represent a certain range of numbers