L02 [Datatypes]

Representations

• Modern computers effectively store patterns of switches that are set On and Off
• We choose representation for numbers, letters, and many other things that are easy to work with

Data Types

• Data representation is the set of values from which a variable, constant, function, or other expression may take its value and includes the meaning of those values
• A data type is a particular representation that has operations in the computer that can operate information that is encoded in that representation

Bits

Bit stands for binary digit

Binary is the most effective way to store and calculate using today's electronics

• Binary-coded decimal flopped

In general, n bits can represent 2^n different states

Binary Tricks

128 64 32 16 8 4 2 1
0    0  1  1 1 1 1 1
0011 1111 = 63

Since this is all 1's, we can just do 64 - 1 to calculate it quickly. (Same idea as 999 is 10000 - 1)

Short-hand math for estimating two's

2^10 ~= 1000
2^32 ~= 4*10^4

Representing negative numbers

Let's observe a pattern

0        0000
1        0001
2        0010
3        0011
4        0100
5        0101
6        0110
7        0111
8        1000

In the last collumn, we see an alternating pattern of 0 1 0 1 0 1 ...

In the penultimate, we see 0 0 1 1 0 0 1 1 ...

Signed Magnitude

• Leftmost bit represents positive or negative
• Problem with -0

00   0
01   1
10  -0
11  -1

One's Complement

• The most intuitive way of representing signed numbers is allocating one bit for the sign
• To make a number negative just flip all the bits

00   0   0
01   1   1
10  -0  -1
11  -1  -0 

Problem: still have the -0 and adding/subtraction operations become very expensive

Two's Complement

To convert, flip all bits and add one

Useful Properties

• There is only one zero
• Arithmetic still works as expected
• First bit still indicates the sign
• Finding the inverse is easy

To do subtraction, just add the two's complement

L02 [Datatypes I]

Review

Which ones to know

• Be able to do math with
  • Unsigned
  • Two's Complement
• Understand these concepts
  • Signed magnitude
  • One's complement
  • Don't have to do math with these

Example problem

Convert 5 - (-2)

5    0101
2    0010
--    ----
7    0111

What is the sum of 101111 and 001010?

101111
001010
------
111001

Overflows (2s comp addition)

• Check carry in and out of the leading digit
  • Most significant digit, on the left
• Add two numbers; we have problems if
  • We get a carry into the sign bit but no carry out
  • We get a carry out of the sign but no carry in
• If we add a positive and negative number we will not have a problem

If we add two positive numbers and we get a carry into the sign we have a problem

If we add two negative numbers and we don’t get a carries into and out of the sign bit we have a problem

Note: carry out and carry in will be different in both cases

Sign Extension

Suppoe we have a number stored in a four bit number and we want to add this number to another number in a 8-bit register.

    0011
01000000
--------
      ??

Perform sign extension by filling in the bits on the left with the sign bit

00000011
01000000
--------
01000011

Fractional Binary Numbers

What is the place value of the first digit to the right of the decimal point in decimal? 10^-1

What is the place value of the first digit to the right of the decimal point in binary? 2^-1

8    4    2    1    ^    0.5        0.25    0.125        0.0625
1    0    1    0        1        1        0            0

1010^1100=10.75