← Back to mit.katmh.com

Binary, Hexadecimal, Two's Complement

· Read 2/17/2021

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. 24-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? [2N1,2N11][-2^{N-1}, 2^{N-1}-1]
  • Most negative: e.g. N=4N=4: Leftmost bit is 23-2^3, so most negative number we can represent is 23-2^3, or 2N1-2^{N-1}
  • Most positive will look like 0111...1110111...111: 20+21+...+2N22^0 + 2^1 + ... + 2^{N-2} = sum of geometric series = 2N112^{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: 2N2^N
  • Two's complement is modular. Regular mod: N bits can represent [0,2N1][0, 2^N - 1]. Here it's shifted over, but the range is the same size: [2N1,2N11][-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