Binary Integers

Unsigned

• Representation of a number through digit sequence to a certain base
• Represents unsigned integers
• Commonly used bases
  • Binary: 2
  • Octal: 8
  • Decimal: 10
  • Hexadecimal: 16
• Base is notated as a subscript
• $\text{Value}=\sum _{i=0}^{n-1}{\text{digit}}_i\cdot {\text{base}}^i$
• One to one mapping to $[0,(B^{\text{n}}-1{)}_{10}]$ (where B is the base and n is the number of digits)
• An example of a non-polyadic system is roman numerals

Converting

• Horner Scheme
  • $Z_B=\sum z_i{B}^i=(((\cdots ((z_{n-1})B+z_{n-2})B+z_{n-3})B+\cdots )B+z_1)B+z_0$
    • This is the same as multiplying each converted digit by $B^i$ but expanded out so it just uses multiplication (using partial sums)
  • Use when the target base is bigger than the source base
  • Steps
    1. Convert every digit to the target base separately
    2. B = source base converted to target base
    3. Compute result in destination system
• Successive Integer Division
  • Uses that all numbers can be represented as $N=qB+r$
    • $r=N\mathrm{mod}B=N-\lfloor \frac{N}{B}\rfloor B$
    • $q=N÷B=N-\lfloor \frac{N}{B}\rfloor$
  • Use when the source base is bigger than the target base
  • Steps
    1. Find the divisor by converting the target base to the source base
    2. Repeatedly integer divide by that (save the remainders) until you only have 0
    3. The remainders make the new representation (most significant digit is the last remainder)
• Binary Shortcuts
  • Binary to Binary Compatible (base is $2^n$)
    1. Break into chunks of ${\log }_{2}B$ digits (from least to most significant bit)
    2. Convert each chunk into a digit in the new number system
  • Binary Compatible to Binary
    1. Convert each digit to their individual binary representation
  • Binary Compatible to Binary Compatible
    1. Convert source to binary
    2. Convert binary to target

Signed

Sign and Magnitude

• The leftmost bit defines the sign of the number (0 positive, 1 negative)
• Range: $-2^{b-1}\dots 2^{b-1}$
• There are two 0s in this representation (one positive and one negative)
• Operations
  • Easy: multiplication, division
  • Hard: addition, subtractions

B’s Complement

• The B’s complement of a n-digit B-adic number N is the n-digit B-adic number that consists of the last n digits of $B^n-N$
• B-complement of n is interpreted as -n

One’s Complement

• The leftmost bit defines the sign of the number (1 negative, 0 positive)
• Conversion
  • If the sign is positive, no more action is needed
  • If the sign is negative, every bit is complemented (flipped)
• Still has two representations of zero

Two’s Complement

• Most common representation
  • because it allows the existing adder to support negative numbers
  • gets rid of the negative 0 problem
• How
  • Positive numbers (in $[0,2^{n-1}-1]$) are represented normally
  • Negative numbers (in $[-2^{n-1},-1]$) are represented with their two’s complement $2^n–|x|$
• Handy mental model
  • Think of the MSB as a negative number and the rest as positive numbers
  • Allows for quickly converting from two’s complement
• Conversion
  • Pad the number with at sign bit to the left
  • If the sign is positive, just convert to binary
  • If the sign is negative, perform 1’s complement and then add 1
    • Shortcut: Leave everything up to the rightmost 1 the same. Complement the remaining bits
• Application: Datapath in modern computers

Excess/Bias

• Changing where you’re centered at
• Subtract an excess from your number to get an actual value
• Excess is halfway through the range
• All 0s = -excess
• Application: Exponent in floating point numbers

Operations

• Addition
  • Digit wise from right to left $x_i+y_i=c_{i-1}$
  • $c_i$ is the carry from digit $i-1$ ($c_{-1}=0$)
  • Carry $c_i$ is propagated to the next left position
  • Overflow
    • Pos + Neg: No Overflow possible
    • Pos + Pos: Overflow if sign bit is 1
    • Neg + Neg: Overflow if sign bit is 0
    • (you know it overflowed if the sign bit flipped)
• Subtraction
  • Addition but apply two’s complement to the second operand
  • Can also do it with one’s complement but if there is an overflow, add 1 to the result
  • Overflow
    • Pos - Pos, Neg - Neg: No overflow possible (same as Pos + Neg)
    • Neg - Pos: Overflow if sign bit is 0 (same as Neg + Neg)
    • Pos - Neg: Overflow is sign bit is 1 (same as Pos + Pos)
• Multiplication
  • Shift and add
    • There are more efficient methods that will be covered later
  • The product of an n-digit number with an m-digit number is an (n+m)-digit number
• Division
  • Long divide but in base 2
  • You can keep going after a decimal point to find the fractional component instead of just having a remainder