http:^^www.cs.wisc.edu^~cs354-2^cs354^lec.notes^represent.html

This data set contains WWW-pages collected from computer science departments of various universities

		       11110000
	      11111111 11110000
	

OVERFLOW
--------

sometimes a value cannot be represented in the limited number
of bits allowed.   Examples:
    unsigned, 3 bits:    8 would require at least 4 bits (1000)
    sign mag., 4 bits:   8 would require at least 5 bits (01000)


when a value cannot be represented in the number of bits allowed,
we say that overflow has occurred.  Overflow occurs when doing
arithmetic operations.

      example:          3 bit unsigned representation

	      011 (3)
	    + 110 (6)
	    ---------
	       ?  (9)     it would require 4 bits (1001) to represent
			  the value 9 in unsigned rep.



CHARACTER REPRESENTATION
------------------------

everything represented by a computer is represented by binary sequences.

A common non-integer needed to be represented is characters.
We use standard encodings (binary sequences) to repreesent characters.

REMEMEBER:  bit patterns do NOT imply a representation


I/O devices work with 8 bit quantities.
A standard code  ASCII (American Standard for Computer Information
Interchange) defines what character is represented by each sequence.

  examples:
    0100 0001  is  41 (hex)  or 65 (decimal).  It represents `A'
    0100 0010  is  42 (hex)  or 66 (decimal).  It represents `B'


    Different bit patterns are used for each different character
    that needs to be represented.

The code has some nice properties.  If the bit patterns are compared,
(pretending they represent integers), then `A' < `B'  
This is good, because it helps with sorting things into alphabetical
order.


Notes:        `a' (61 hex)  is different than `A' (41 hex)
              `8' (38 hex) is different than the integer 8

    the digits:
	  `0' is 48 (decimal) or 30 (hex)
	  `9' is 57 (decimal) or 39 (hex)


Because of this, you have to be careful.  Consider the following example:


       in1:  .byte
       result:  .byte


	     get in1
	     add  result, in1, in1
	     put result



    suppose the user types `3'
       result <-  51 + 51 = 102 (decimal)

       put prints out `f', since the ASCII code for 102(decimal) is `f'


What we really wanted was more likely this:

       in1:     .byte
       number:  .word
       result:  .word
       out1:    .byte


	     get  in1
	     sub  number, in1, 48
	     add  result, number, number
	     add  out1, result, 48
	     put  out1

  the subtract takes the "bias" out of the character representation.
  the add puts the "bias" back in.


This will only work right if the result is a single digit.
        (What would happen if it wasn't?)

What we need is an algorithm for translating character strings
to the integers they represent, and visa versa.


ALGORITHM:   character string --> integer
   the steps:

      for `3' `5' `4'

      read `3'
      translate `3' to 3

      read `5'
      translate `5' to 5
      integer =  3 * 10  + 5 = 35

      read `4'
      translate `4' to 4
      integer =  35 * 10  + 4 = 354

  the algorithm:
     
     integer = 0
     while there are more characters
       get character
       digit <-  character - 48
       integer <- integer * 10  + digit


ALGORITHM:  integer --> character string
   the steps:
   for 354, figure out how many characters there are (3)

   354 div 100 gives 3
   translate 3 to `3' and print it out
   354 mod 100 gives 54

   54 div 10 gives 5
   translate 5 to `5' and print it out
   54 mod 10 gives 4

   4 div 1 gives 4
   translate 4 to `4' and print it out
   4 mod 1 gives 0, so you're done




REPRESENTATION OF FLOATING POINT NUMBERS
----------------------------------------

computers represent real values in a form similar to that of
scientific notation.  There are standards which define what the
representation means so that across computers there will be consistancy.

Note that this is not the only way to represent floating point
numbers, it is just the IEEE standard way of doing it.

Here's what we do:

the representation

	 -------------------
	 | S |   E   |  F  |
	 -------------------

    S is one bit representing the sign of the number
    E is an 8 bit biased integer representing the exponent
    F is an unsigned integer

 the true value represented is:

              S        e
	  (-1)  x f x 2

 where
	    e = E - bias
                   n
	    f = F/2  + 1
 
 for single precision numbers (the emphasis in this class)
       n = 23
       bias = 127



Now, what does all this mean?
  --> S, E, F all represent fields within a representation.  Each
      is just a bunch of bits.

  --> S  is just a sign bit.  0 for positive, 1 for negative.

  --> E  is an exponent field.   The E field is a biased-127 representation.
      So, the true exponent represented is (E - bias).  The radix for
      the number is ALWAYS 2.

      Note:  Computers that did not use this representation, like those
	     built before the standard, did not always use a radix of 2.
	     Example:  some IBM machines had radix of 16.

  --> F  is the mantissa.  It is in a somewhat modified form.  There are
      23 bits available for the mantissa.  It turns out that if fl. pt.
      numbers are always stored in their normal form, then the leading
      bit (the one on the left, or MSB) is always a 1.  So, why store
      it at all?  It gets put back into the number (giving 24 bits
      of precision for the mantissa) for any calculation, but we only have
      to store 23 bits.

      This MSB is called the HIDDEN BIT.


An example:   put the decimal number 64.2 into the standard single
	      precision representation.
	
	first step:
	  get a binary representation for 64.2
	  to do this, get binary reps. for the stuff to the left
	  and right of the decimal point separately.

	  64  is   1000000

	  .2 can be gotten using the algorithm:

	  .2 x 2 =  0.4      0
	  .4 x 2 =  0.8      0
	  .8 x 2 =  1.6      1
	  .6 x 2 =  1.2      1

	  .2 x 2 =  0.4      0  now this whole pattern (0011) repeats.
	  .4 x 2 =  0.8      0
	  .8 x 2 =  1.6      1
	  .6 x 2 =  1.2      1
	    

	    so a binary representation for .2  is    .001100110011. . .



	Putting the halves back together again:
	   64.2  is     1000000.0011001100110011. . .


      second step:
	normalize the binary representation. (make it look like
	scientific notation)

				  6
	1.000000 00110011. . . x 2

      third step:
	6 is the true exponent.  For the standard form, it needs to
	be in biased-127 form.

	      6
	  + 127
	  -----
	    133

	133 in 8 bit, unsigned representation is 1000 0101

	this is bit pattern used for E in the standard form.

      fourth step:
	the mantissa stored (F) is the stuff to the right of the radix point
	in the normal form.  We need 23 bits of it.

	  000000 00110011001100110


      put it all together (and include the correct sign bit):

	 S     E               F
	 0  10000101  00000000110011001100110

      the values are often given in hex, so here it is

	 0100 0010 1000 0000 0110 0110 0110 0110

     0x   4    2    8    0    6    6    6    6



Some extra details:

 -->  Since floating point numbers are always stored in normal
      form, how do we represent 0?

       (What does the fl. pt. number 0x3f80 0000 represent?)

      We take the bit patterns 0x0000 0000 and 0x8000 0000
      to represent the value 0.

       (What fl. pt. numbers cannot be represented because of this?)

 -->  Other special values:

       +infinity     0 11111111 00000... (0x7f80 0000)
       -infinity     1 11111111 00000... (0xff80 0000)

       NaN (Not a Number)     ? 11111111 ?????... 
	  (S is either 0 or 1, E=0xff, and F is anything but all zeros)

</pre>