# Outline of Class 34: Introduction to Machine Representation

Held: Friday, April 3, 1998

• Don't forget about all the wonderful Chris Haynes events on Friday.
• Any questions on assignment 5? Note that the due date has been corrected (and at least one of you has come pretty close to finishing).

## Binary Representation

• It turns that that we're very good at building electronic devices that can represent pairs of values. We call such devices binary devices and generally refer to the values they represent as 0 and 1. Each value is called a bit.
• All of computing can be done with intelligent use of bits and circuitry.

### Representing Fundamental Types

• We normally speak of primitive types like integers, floats, and such.
• These types are built into the language.
• But they need to be implemented at some level (in compiler, virtual machine, or hardware).
• In most machines, values are stored as fixed-length sequences of bits (0/1 values).
• Bits are grouped into bytes and words.
• Typically, a byte is eight bits
• Typically, a word is some multiple of bytes, usually two or four bytes.
• The bits in a group are numbered from right to left, starting with 0.
• The rightmost bit in an eight-bit byte is the 0th bit.
• The leftmost bit in an eight-bit byte is the 7th bit.
• Observe that there are (at least) three versions of each number:
• The pure, mathematical entity.
• The representation in ASCII text (or which there may be many)
• The representation in binary (of which there is at most one)

### Integers

• It is easy to represent positive integers as standard binary numbers. The rightmost bit is the 1's column (1=2^0), the next is the 2's column (2=2^1), the next is the 4's column(4=2^2), and so on and so forth.
• Addition and multiplication are stratighforward for this representation (and surprisingly easy to represent in circuitry).
• However, if we limit the number of bits per integer, we have to allow for overflow when more bits are needed to represent the results than the operands.
• But what happens when we need to represent negative integers? What makes a representation scheme good?
• Only one representation for each number (or at most two for some numbers).
• Represents a wide range of values.
• Easy to use in computation (preferably, using the aforementioned routines or simple variants).
• What are strategies for representing negative integers? They include signed magnitude, one's complement, two's complement, and excess 2^(m-1).
• Signed magnitude. Use the leftmost bit to indicate the sign.
• Positive numbers begin with 0, negative numbers begin with 1.
• There are two representations of 0 (+0 and -0).
• With eight bits, you can represent everything between -127 and +127.
• Negation is easy.
• But addition and subtraction are hard.
• One's complement. To negate a number, flip the bits (0 to 1, 1 to 0).
• Positive numbers begin with 0, negative numbers begin with 1.
• There are two representations of 0 (00000000 and 11111111 in eight-bit).
• With eight bits, you can represent everything between -127 and +127.
• Negation is easy, but slightly time consuming.
• It's not clear that addition and subtraction are any easier.
• Two's complement. To negate a number, flip the bits and then add 1, using standard addition. Throw away any overflow bits.
• Positive numbers begin with 0. Negative numbers begin with a 1.
• There is only one representation of 0 (00000000 to 11111111 add 1, giving 100000000, but the 1 is an overflow).
• Negation is easy, but time-consuming (n flips, up to n steps in the addition).
• Surprisingly, the standard binary addition routine works.
• Excess 2^(m-1). To represent x, instead represent x+2^(m-1) using the positive-only representation (where m is the number of bits in the representation).
• This is sometimes called a biased representation.
• Positive numbers begin with 1. Negative numbers begin with 0.
• There is only one representation of 0, 10000000.
• The largest number we can represent is 11111111 = 127.
• The smallest number we can represent is 00000000 = -128
• How do you do negation?
• How do you do addition?

On to More Binary Representation
Back to Fun with Applets and Graphics
Outlines: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Current position in syllabus

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.