CP1300 Binary Data

Storage and Number Systems

• Storage
  • Data is stored as a collection of bits (0's and 1's)
  • 8 bits = 1 byte
  • N (2,4, ...) bytes = 1 word
  • A kilobyte (KB) is 2¹⁰ = 1024 bytes
  • A megabyte (MB) is 2²⁰ bytes

• Number Systems
  • Computers use the binary number system (base 2)
  • The value of the number 2468₁₀ is given by :
    2468₁₀ = 2 x 10³ + 4 x 10² + 6 x 10¹ + 8 x 10⁰
  • The value of a binary number 1101₂ is given by:
    1101₂ = 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰ = 13
  • 2ⁿ numbers can be stored in n bits
  • Note that the rightmost bit indicates the parity in binary.
  • Octal (base 8) digits are 0 to 7.
  • Hexadecimal (base 16) digits are 0 to 9, and A (10), B (11), C (12), D (13), E (14), F (15)

• Converting between Number Systems
  • Converting from decimal to base b
    • Repeatedly divide by b, writing down the remainders in reverse order
    • Example, converting 75₁₀ to binary

      Base Num Rem
         2  75 
            37   1
            18   1
             9   0
             4   1
             2   0
             1   0
             0   1
      

      Therefore 75₁₀ = 1001011₂.
    • Example, converting 1179₁₀ to hexidecimal

      Base  Num Rem
        16 1179 
             73   B
              4   9
              0   4
      

      Therefore 1179₁₀ = 49B₁₆.
  • Converting from base b to decimal

    • Set Total to 0
      For each digit, from left to right
          Multiply Total by b and add the value of the digit
      

    • Example, converting 1001011₂ to decimal

      Base Total Digit
         2     0     1
               1     0
               2     0
               4     1
               9     0
              18     1
              37     1
              75 
      

      Therefore 1001011₂ = 75₁₀.
    • Example, converting 49B₁₆ to decimal

      Base Total Digit
        16     0     4
               4     9
              73     B
            1179
      

      Therefore 49B₁₆ = 1179₁₀.
  • Converting binary to octal and hexidecimal
    • Octal, group the bits into threes
    • Hex, group the bits into fours
    • Example, 75₁₀ = 1001011₂
      • Grouping into 3's (octal) 001 001 011 = 113₈
      • Grouping into 4's (hex) 0100 1011 = 4B₁₆

Character Representation

• Typically stored in 1 byte using an agreed standard about which patterns represent which characters
• ASCII = American Standard Code for Information Interchange
  • 7-bit code for alphabetic and numeric characters (128 symbols)
  • Developed by ANSI (American National Standards Institute)
  • The most common format for text files
• EBCDIC = Extended Binary-Coded Decimal Interchange Code
  • 8-bit code for alphabetic and numeric characters (256 symbols)
  • IBM developed it for their earlier large operating systems
• ASCII.cpp - Converting characters to integer values

Integer Representation

• Unsigned Integers
  • Can represent 0 to 2ⁿ-1 using n bits
  • Addition
    • Adding bits
      • 0 + 0 = 0
      • 0 + 1 = 1
      • 1 + 0 = 1
      • 1 + 1 = 0 carry 1
    • Example

        0 1 0 1 0 0 1 1
      + 0 1 0 1 0 1 0 1
        ---------------
      = 1 0 1 0 1 0 0 0
      C 0 1 0 1 0 1 1 1
      

  • Subtraction
    • Don't bother, better representations coming that cope with negative numbers
  • Multiplication
    • Shift-add multiplication

      Set the Result to 0
      For each bit of the Multiplier, from right to left, do
          If the bit is 1 then 
              Add Mulitplicand to Result
          Shift the Multiplicand left one bit
      

    • Example, 11 * 5

      Bit Multiplicand   Result
                       00000000
        1     00000101 00000101
        1     00001010 00001111
        0     00010100 00001111
        1     00101000 00110111
        0     01010000 00110111
        0     10100000 00110111
        0     01000000 00110111
        0     10000000 00110111
      

      Thus 11 * 5 = 55
    • Shifting left multiplies by 2
    • Shifting is typically a hardware operation
  • Division
    • Algorithm for N bits takes requires 2N bit register
    • Based on shifting right (dividing by 2)

• Signed-magnitude Integers
  • The top bit specifies the sign: 0 = positive, 1 = negative.
  • n-1 bits are available for the magnitude of the integer
  • The range of values is -(2^n-1-1) to 2^n-1-1
    • This is only 2ⁿ - 1 different numbers.
  • There are two representations for 0

• Biased (or excess) Integers
  • Add 2^n-1 to the number and convert to binary.
  • The range of values is -2^n-1 to 2^n-1-1
  • The top bit gives the sign: 1 = positive, 0 = negative
  • This is 2ⁿ different numbers.

• Ones Complement Integers
  • Store the magnitude of the number unsigned
  • If the number is negative invert all bits
  • The top bit gives the sign: 0 = positive, 1 = negative.
  • The range of values is -(2^n-1-1) to 2^n-1-1.
    • This is only 2ⁿ - 1 different numbers.
  • There are two representations for 0

• Twos Complement Integers
  • Store the magnitude of the number unsigned
  • If the number is negative then invert all bits and add 1
  • The top bit gives the sign: 0 = positive, 1 = negative.
  • To convert to decimal from 2's complement
    • Check the sign bit
    • If 0 then convert as usual
    • If 1 apply 2's complement and convert, then negate
  • The range of values is -2^n-1 to 2^n-1-1.
  • This is 2ⁿ different numbers.
  • Addition
    • Addition is as for unsigned integers
    • Example, 15 + 9

        0 0 0 0 1 1 1 1
      + 0 0 0 0 1 0 0 1
        ---------------
      = 0 0 0 1 1 0 0 0
      C 0 0 0 0 1 1 1 1
      

      Therefore 15 + 9 = 24
  • Subtraction
    • A - B is equivalent to A + (-B)
    • Example, 15 - 9

        0 0 0 0 1 1 1 1
      + 1 1 1 1 0 1 1 1
        ---------------
      = 0 0 0 0 0 1 1 0
      C 1 1 1 1 1 1 1 1
      

      Therefore 15 - 9 = 6
    • Overflow has occurred if the sign of both numbers is the same, but the sign of the result is different.
  • Mulitplication and Division
    • As for unsigned integers, with signs dealt with separately

Real Number Representation

• Fixed point notation
  • The top bit specifies the sign (as in signed magnitude): 0 = positive, 1 = negative.
  • Some are bits used for the integer part, in the normal way
  • Some bits are used for the fractional part
    • The fractional columns are 2^-1, 2^-2, ...
    • To convert the fractional part

      Repeat
          Multiply the number by 2
          Write down and discard the integer part 
          Until the number reaches 0
      

  • Example, -37.90625
    • Sign bit is 1
    • Integer part

      Base Num Rem
         2  37 
            18   1
             9   0
             4   1
             2   0
             1   0
             0   1
      

      Therefore the integer part is 100101
    • Fractional part

      Base     Num Int
         2 0.90625 
           1.8125    1
           1.625     1
           1.25      1
           0.5       0
           1.0       1
           0 
      

      Therefore the fractional part is 11101
    • -37.90625₁₀ = 1100101.11101₂
  • Problem is how many bits to assign to integer and fractional parts
    • More bits in integer part allows larger magnitude numbers
    • More bits in fractional part is more accurate
    • Some decimal fractions have infinite binary representations
      • Example, 0.4

        Base Num Int
           2 0.4
             0.8   0
             1.6   1
             1.2   1
             0.4   0
             0.8   0
             etc
        

• Scientific Notation
  • Example -37.90625₁₀ = -0.3790625E+2₁₀
  • The format is Sign Significand E Exponent
  • The signed significand is multiplied by Base^Exponent
  • Any number can be normalized so it starts 0.
  • This can be done base 2
  • Example, 37.90625₁₀ = 100101.11101₂ = 0.10010111101 * 2⁶

• Floating Point Representation
  • The top bit specifies the sign: 0 = positive, 1 = negative.
  • Some are bits used for the exponent, in biased notation
  • Some bits are used for the significand
    • Every normalized significand starts 0.1
    • The 0.1 is not stored, i.e., one free bit
  • Example, -37.90625, 7 bit exponent, 8 bit significand
    • Sign bit is 1
    • Exponent is 1000110
    • Significand is 00101111
  • More bits in the exponent part allows larger and smaller magnitude numbers
    • Very large numbers cannot be represented - overflow
    • Numbers close to 0 cannot be represented - underflow
    • 0 cannot be stored, due to the implicit 0.1. How is this handled?
  • More bits in the significand is more accurate
  • Typically, there might be 8 bits in the exponent, and 23 bits in the significand (plus 1 bit for the sign) gives you a 32 bit floating point number.

Self assessments

• Data Representation

Tutorial Questions

• Data Representation (Answers)
• Number Systems (No answer available)

Exam style questions

1. State three standard ways to organise bits into collections of bits.
2. What is the general principle used to represent other types of information?
3. Name two character representation schemes, briefly explaining each.
4. Name and briefly explain three techniques for representing integers as binary numbers. State any problems these representations may have.
5. When is hexadecimal a useful alternative to binary?
6. What are two techniques for representing real numbers in binary?
7. For the following answer true or false:
   • 5 bit signed magnitude:
     • 11011 = 11
     • 00110 = +6
     • The smallest negative number that can be stored is: -15
     • The largest positive number that can be stored is: +15
   • 6 bit biased:
     • The bias is: 32
     • 101101 = 13
     • 011110 = -2
     • The largest positive is: 31
     • The smallest negative is: -32
   • 5 bit Two's Complement:
     • 00000 = 0
     • 00101 = 7
     • 11010 = -6
     • 10100 + 01110 = 00010
     • The largest positive is: +15
     • The binary number representing the smallest negative number is: 11111
   • Unsigned Fixed point:
     • 1011.101 = 11.625
     • 0.000001 = 0.015625
     • Fixed point is useful for representing very large numbers and very small fractions.
   • 6 bit Signed Floating point: 1bit sign, 3bit exponent, 2bit significand
     • 1 010 11 is the same as the fixed point: -0.00111 (and this is?!)
     • 0 111 00 is: +4
     • The largest positive is: +7
     • The largest negative is: -0.03125