Class 09: Representing Integers

Held: Monday, 3 February 2003

Summary: Today we consider a variety of mechanisms for representing integers as a sequence of bits.

Related Pages:

• EBoard.
• Representing Integers.

Assignments:

• Homework 4: Binary to Decimal and Back Again (due Fri).
• Read Gries, Chapter 4 (due Tue).
• Read IEEE Floating Point Representation.

Notes:

• Any suggested improvements to the reading?

Overview:

• Binary representation.
• Unsigned binary integers.
• Computing with unsigned binary integers.
• Signed binary integers.
• Computing with signed binary integers.

Introduction to Binary

• As you may recall from out discussion of simple models of computing, a key aspect of most models of computing is memory.
  • We'll have memory include both main memory and the registers (and many other forms of memory).
• As you may know, memory on most computers is effectivel a bunch of switches that can be in one of two states: off (0) or on (1).
• Hence, every value in memory is stored as a sequence of 0's and 1's.
• The type of a value determines how we interpret each sequence of 0's and 1's.
• For convenience, we typically reserve a fixed number of bits for each type (in most modern architectures, that number of bits is a power of 2, such as 8, 16, 32, or 64).
• What should we care about in designing these encodings in binary?
  • They should be relatively efficient (in that it doesn't require many bits to represent a value).
  • It should be relatively easy to convert into and from binary.
  • For numeric values, it should be relatively easy to compute.

Unsigned Binary Integer

• One of the first kinds of values we learn how to represent is the unsigned binary integer.
• As in standard unsigned decimal integers, each column has a particular value:
  • The rightmost column is the one's column (1 = 2⁰ ).
  • The column to its left is the two's column (2 = 2¹).
  • The column to its left is the four's column (2 = 2²).
  • The column to its left is the eight's column (2 = 2³).
  • And so on and so forth.
• Is this encoding efficient? For an n-bit encoding, we can represent 2ⁿ different values.
  • I'm not sure you can do better than that.
  • You can certainly do worse.
• Is it easy to decode this encoding? Certainly. A simple for loop should do it.
• Is it easy to encode? Fairly, although the first time you try to write this algorithm you may encounter some difficulties if you're not careful.
  • One natural algorithm works left-to-right in the binary notation. (If the number is odd, put a 1 in the current position and subtract 1. Otherwise, put a 0 in the current position. Divide by 2 and continue.)
  • Another algorithm works right to left.
• Is it easy to compute? Let's try addition.

Unsigned Binary Addition

• We all know the standard algorithm for adding in decimal:
  • Add each column from right to left, adding a carry digit if the sum gets too large.
  • We can apply the same algorithm in binary.
• How should we implement it? Probably in hardware.
  • Rightmost column: Two inputs (a₀ and b₀ ), two outputs (carry₁ and sum₀).
  • carry₁ = and(a₀,b₀)
  • sum₀ = or(a₀,b₀)
  • Remaining columns: Three inputs (a_i, b_i, and carry_i), two outputs (carry_i+1 and sum_i)
  • Hardware implementation left to your creativity.

Other Unsigned Operations

• What other numeric algorithms might we implement?
• Multiplication:
  • Can be implemented by repeated addition (not very efficiently).
• Note that to multiply by a power of two, we simply shift by the appropriate number of bits.
  • Hence, we can multiply with #bits additions plus #bits shifts.
• Subtraction:
  • Might be implemented in the standard way
  • But borrowing is a pain-in-the-nec
• Is there a better subtraction algorithm?
  • Negate and add (if you design things right)!
• Whoops, if we negate, we need to represent negative numbers.

Signed Integers

• We need to represent negative numbers.
  • What techniques can we use?
  • How will we evaluate those techniques?
• You should know a variety of techniques from the reading.
• We can evaluate the techniques using the criteria described above:
  • Efficiency of representation
  • Ease of converting to and from binary
  • Ease of computation
• Most people's first attempt: Signed magnitude.
  • Leftmost bit gives sign. Other digits as in unsigned.
  • Easy to create.
  • Two versions of 0.
  • Easy to negate (flip leftmost bit).
  • Hard to add.
• Interesting second attempt: One's complement.
  • Negate by flipping all bits.
  • Pretty easy to create.
  • Two versions of 0.
  • Standard addition doesn't quite work right. (I've forgotten the precise extra trick you need, but I think it's something like: If there's an overflow carry bit, add it to the rightmost column.)
  • Leftmost bit still gives sign.
• Odd variant: Two's complement
  • Negate by flipping all the bits and adding 1. (Can you prove that double negation has no effect?)
  • Slightly harder to create and interpret.
  • Only one version of 0.
  • Add using standard unsigned technique.
  • Leftmost bit still gives sign.
• Still odder: Excess 2^m-1
  • When using m-bit numbers, add 2^m-1 before encoding, and then encode as unsigned integers.
  • To negate: Flip all the bits and add 1. (Prove it?)
  • To add: Add using unsigned and flip leftmost bit (Prove it?)
  • Leftmost bit still gives sign (although 1 is now positive and 0 is now negative).