Number Bases

Already learned in CSAPP

Signed Representations

Signed Intergers

  • n bits => $2^n$ things
    – half positive, half negative?

Sign and Magnitude

  • “first” bit gives sign, rest treated as unsigned(magnitude)
  • below is an example
    • $000_2 = +0_{10}$
    • $001_2 = +1_{10}$
    • $010_2 = +2_{10}$
    • $011_2 = +3_{10}$
    • $100_2 = -0_{10}$
    • $101_2 = -1_{10}$
    • $110_2 = -2_{10}$
    • $111_2 = -3_{10}$

Zero

$(0……0)_2$ and $(1……0)_2$ = $\pm0$

Most pos number

$(01……1)2 = (2^{(n-1)}-1){10}$

Most neg number

$(1……1)2 = -(2^{(n-1)}-1){10}$

Increment

not quite ideal.

Biased Notation

  • Like unsigned, but “shifted” so zero is (roughly) in the middle
  • below is an example
    • value = “unsigned value” - bias
    • conventional bias : $(2^{n-1}-1)$
    • $000_2 = -3_{10}$
    • $001_2 = -2_{10}$
    • $010_2 = -1_{10}$
    • $011_2 = 0_{10}$
    • $100_2 = 1_{10}$
    • $101_2 = 2_{10}$
    • $110_2 = 3_{10}$
    • $111_2 = 4_{10}$

Zero

$01……1_2 = 0_{10}$

Most neg number

$0……0_2 = -(2^{(n-1)-1})_{10}$

Most pos number

$1……1_2 = 2^{(n-1)}_{10}$

Increment

just like unsigned(sorta).

One’s Complement

  • New negation procedure - complement the bits:
  • the idea is neg numbers are generaeted by flipping or complementing the bit, which means all 0 will be turned into 1 and all 1 will be turned into 0.
  • below is an example
    • $000_2 = +0_{10}$
    • $001_2 = +1_{10}$
    • $010_2 = +2_{10}$
    • $011_2 = +3_{10}$
    • $100_2 = -3_{10}$
    • $101_2 = -2_{10}$
    • $110_2 = -1_{10}$
    • $111_2 = -0_{10}$

Zero

$0……0_2$ and $1……1_2$ = $\pm0_{10}$

Most neg number

$1……0_2 = -(2^{(n-1)}-1)_{10}$

Most pos number

$01……1_2 = (2^{(n-1)}-1)_{10}$

Increment

  • kind of like unsigned
  • a weird edge case where if the most significant bit overflows or there is a carryout,we have to wrap around and add that to the beginning of the number. AND THIS IS REALLY COMPLICATED .

Two’s Complement

  • Like One’s Complement, but “shift” negative #s by 1:
  • Two’s Complement take the idea of One’s Complement where we complement or negate the bits, but then it adds 1
  • So to get the neg number, we take the pos value, negate the bits and then add 1
  • below is an example
    • $000_2 = +0_{10}$
    • $001_2 = +1_{10}$
    • $010_2 = +2_{10}$
    • $011_2 = +3_{10}$
    • $100_2 = -4_{10}$
    • $101_2 = -3_{10}$
    • $110_2 = -2_{10}$
    • $111_2 = -1_{10}$

Zero

$0……0_2$ = $\pm0_{10}$

Most neg number

$1……0_2 = -2^{(n-1)}_{10}$

Most pos number

$01……1_2 = (2^{(n-1)}-1)_{10}$

Increment

JUST LIKE UNSIGNED!

Summary

  • Used by all modern hardware
  • Roughly evenly split between positive and negative
    • one more negative # becase pos side has 0
  • Can still use MSB as sign bit
  • To negate: Flip the bits and add one

Overflow

Numbers in a Computer

  • Numbers really have ∞ digits,but hardware can only store a finite number of them(fixed)
    • Usually ignore leading zeros
    • Leftmost is most significant bit(MSB)
    • Rightmost is least significant bit(LSB)

Overflow

  • Overflow is when the result of an arithmetic operation can’t be represented by the (FINITE) hardware bits
    • i.e. the result is mathematically incorrect
  • Examples:
    • Unsigned: 0b1…1 + 1 = 0b0…0 = 0 ?
    • Two’s: 0b01…1 + 1 = 0b1…0 = $(-2^{(n-1)})_{10}$
  • Solution add more bits

Sign Extension

  • Want to represent the same number using more bits than before
    • Easy for positive #s(add leading 0’s),more complicated for negative #S
    • Sign and magnitude: add 0’s after the sign bit
    • One’s complement: copy MSB
    • Tow’s complement: copy MSB
  • Example:
    • Sign and magnitude: 0b11 = 0b1001
    • One’s / Two’s complement: 0b11 = 0b1111;

Summary

Number Representation: How to represent positive and negative integers using binary

  • Unsigned: Interpret numeral in base 2
  • Signed: Two’s Complement
  • Biased: Add bias
  • Sign extension must preserve signed number

Conversions

  1. Hex <–> Binary <–> Decimal(easy for translating)
  2. Remember the decimal $2^0$ to $2^{10}$
  3. kb: $2^{10}$, mb: $2^{20}$, gb: $2^{30}$, tb: $2^{40}$, pb: $2^{50}$, eb: $2^{60}$, zb: $2^{70}$, yb: $2^{80}$

go from a smaller base to a larger base

……

go from a larger base to a smaller base

……

Binary to Hex

……

Hex to Binary

……

bias notation

unsigned value + bias = actual value

Two’s complement

  1. the sign bit is neg and all other bits are pos
  2. Fliping bits (except sign bit) and add 1

Unsigned and Tow’s complement addition

doing addition for unsigned and Tow’s complement is the same
but how you interpret the value is different

overflow

unsigned

positive overflow……

Tow’s complement

positive overflow & negetive overflow……

Questions

Take the 4-bit number x = 0b1010.
Calculate the value represented in the following schemes

schemes value
unsigned $2^3+2^1 = 10$
sign and magnitude $-1*2^1 = -2$
biased notation $2^3 + 2^1 - (2^3 - 1) = 3$(conventional bias : $(2^{n-1}-1)$)
one’s complement -x = ~x = 0b0101 = 5 ==> x = -5
two’s complement -x = ~x + 1 = 0b0101 + 1 = 0b0110 = 6 ==> x = -6

Review

  • Bits can be used to represent anything!
  • n bits can represent up to 2n things
  • Number Representation
    • Unsigned, Bias, 1’s, 2’s
    • Overflow
    • Sign Extension