Last Updated: 2019-09-17 Tue 20:05

CSCI 2021 Lab03: Binary Integers

CODE DISTRIBUTION: lab03-code.zip

  • Download the code distribution every lab
  • See further setup instructions below

CHANGELOG:

1 Rationale

Modern computers represent all data using bits, collections of 1's and 0's. Integer data pervades many applications so understanding the bit-level representation of integers lends insight into their strengths and limitations. The two's complement representation for integers is by far the most common used by hardware and is therefore considered specially in this lab. C provides facilities to manipulate data at the bit level using logical and shift operations which are also discussed.

Associated Reading / Preparation

Bryant and O'Hallaron: Ch 2.1-2.3 on binary representations of integers in unsigned and two's complement signed format.

Grading Policy

Credit for this lab is earned by taking the associate Lab Quiz which is linked under Canvas / Assignments. The quiz will ask that you upload your completed QUESTIONS.txt document and then take a short quiz on the material covered in the lab.

See the full policy in the syllabus.

2 Codepack

The codepack for the lab contains the following files:

File Description
QUESTIONS.txt Questions to answer
convert.c C file for Problem 3
twos_complement.c Simple demonstration of C code for twos complement

3 Two's Complement Arithmetic

Your lab leader will discuss the basics of two's complement representation of integers at the beginning of the lab. Understanding two's complement is necessary to complete a problem QUESTIONS.txt.

The principles of two's complement representation for integers are as follows.

  • Fix a number of bits to represent integers such as 8 bits or 32 bits
  • Zero is the bit string of all 0s. In 8 bits this is

    0000 0000
    
    
  • Positive numbers always start with a 0. In 8 bits +91 would be

    0101 1011
    
    
  • Negative numbers always start with a 1. In 8 bits, the following is a negative number

    1010 0101
    
    
  • To determine the value of negative number in two's complement or negate it:

    1. Invert the bits: ones become zeros, zeros to ones. The C operator invert is the tilde ~ symbol.
    2. Add 1

    This process on the above negative number is as follows.

    ~ 1010 0101 = negative number
    -----------
      0101 1010 = +90
    +         1
    -----------
      0101 1011 = +91
    

    So the above negative number is -91 as 91 is its twos complement.

  • The same process works to convert from positive to negative.

    ~ 0101 1011 = +91
    -----------
    ~ 1010 0100 = negative number
    +         1
    -----------
    ~ 1010 0101 = -91
    

    So the above negative number is -91 as 91 is its twos complement.

  • C's unary negation operator performs these two steps of inverting and adding 1:

    int p = 91;  // 0101 1011
    int n = -p;  // 1010 0101
    
    
  • The context for interpreting bits matters. When interpreting bits as an unsigned quantity, each bit represents a power of 2 that should be added.

    unsigned char p = 0b10100101;
    //   1   0    1   0   0   1   0   1
    // 128 + 0 + 32 + 0 + 0 + 4 + 0 + 1
    // = 165
    
  • In contrast, the same bits when interpreted in a signed context are a negative quantity. In the 2's complement representation, the highest order bit is associated with a negative power of two.

    char p = 0b10100101;  // signed quantity, negative due to leading 1
    //    1   0    1   0   0   1   0   1
    // -128 + 0 + 32 + 0 + 0 + 4 + 0 + 1
    // = -91
    
  • Due to 0 starting with a 0, there is one more bit string available for negative numbers than for positive numbers. This explains the asymmetric range of C data types. 8-bit characters have a range of -128 to +127 which are the following bit strings

    +127 = 0111 1111
    -128 = 1000 0000
    
  • Arithmetic in twos complement has some nice properties such as going from 0 to -1:

      0000 0000 = zero
    + 1111 1111 = -1
    -----------
      1111 1111 = -1
    

    More details of arithmetic will be discussed later.

  • For wider bit widths than 8, extend the sign bit for numbers left as in the following

     8-bit +91: 0101 1011
    16-bit +91: 0000 0000 0101 1011
     8-bit -91: 1010 0101
    16-bit -91: 1111 1111 1010 0101
    
    

4 What to Understand

Ensure that you understand

  • Signed vs unsigned representations
  • Two's complement representation of integers
  • Conversions between binary, decimal, octal, and hexadecimal notation

5 Questions

Analyze the files in the provided codepack and answer the questions given in QUESTIONS.txt.

                           __________________

                            LAB 03 QUESTIONS
                           __________________


- Name: (FILL THIS in)
- NetID: (THE kauf0095 IN kauf0095@umn.edu)

Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.


PROBLEM 1: Number conversions
=============================

A
~

  Fill in the following table of equivalences.  Filling in the table
  from top to bottom is advantageous as earlier rows can sometimes be
  used to infer lower values. Feel free to make use of any ASCII table
  or the table.c program provided in the week 3 lecture code pack.

  ,----
  | |-----+------+-----+-----------+--------------|
  | | Dec | Hex  | Oct | Binary    | Char         |
  | |-----+------+-----+-----------+--------------|
  | |   9 | 0x09 |  11 | 0000 1001 | TAB          |
  | |  10 | ?    |   ? | ?         | \n (newline) |
  | |   ? | 0x20 |   ? | ?         | SPACE        |
  | |   ? | ?    |   ? | 0011 0010 | ?            |
  | |  65 | 0x41 | 101 | 0100 0001 | A            |
  | |  66 | ?    |   ? | ?         | ?            |
  | |   ? | 0x4F | 117 | ?         | O            |
  | |  80 | ?    |   ? | ?         | P            |
  | |  91 | ?    | 133 | 0101 1011 | [            |
  | |  97 | 0x61 | 141 | ?         | ?            |
  | |   ? | ?    | 172 | 0111 1010 | z            |
  | | 145 | 0x91 | 221 | ?         | none         |
  | | 160 | ?    |   ? | 1010 0000 | none         |
  | | 180 | 0xB4 | 264 | ?         | none         |
  | | 255 | ?    |   ? | ?         | none         |
  | |-----+------+-----+-----------+--------------|
  `----


B
~

  Fill in the bits, hex, and decimal values for the given examples. The
  first example is completed for you. Assume all of these are 32 bit
  unsigned integers.
  ,----
  |   COMPLETED
  |   Binary:   0000 0000  0000 0000  0001 1000  1110 1001  
  |             0    0     0    0     1    8     E    9
  |   Hex   :   0018E9
  |   Decimal:  6377
  | 
  | 
  |   NUMBER 1
  |   Binary:   0000 0000  0010 1111  0011 1010  1000 1101  
  |             ?
  |   Hex   :   ??
  |   Decimal:  ??
  | 
  | 
  |   NUMBER 2
  |   Binary:   ??  
  |             7    F     8    3     5    A     0    B
  |   Hex   :   7F835A0B
  |   Decimal:  ??
  `----


PROBLEM 2: Signed Integer Conversions
=====================================

A
~

  Apply the steps involved in converting the following positive binary
  number to it's two's complement negation in 8-bit signed
  format. Recall the steps are
  - Invert the bits
  - Add one
  Apply these steps to the following number:
  ,----
  | 0111 1100  = 0x7C = 124 (decimal)
  `----
  The result is the two's complement representation of -124.

  Convert back to positive via the same process
  - Invert the bits
  - Add one
  to show that the original bits are gotten back.


B
~

  Complete the following table of equivalences assuming 8-bit
  twos-complement signed integers. The rightmost column is the inverse
  of the binary representation: flip 1's to 0's, and vice versa.

  ,----
  | |------+------+-----------+-----------|
  | |  Dec |  Hex | Binary    | Inverse   |
  | |------+------+-----------+-----------|
  | |   +5 | 0x05 | 0000 0101 | 1111 1010 |
  | |   -5 |    ? | 1111 1011 | ?         |
  | |  +32 | 0x20 | ?         | ?         |
  | |  -32 | 0xE0 | ?         | 0001 1111 |
  | | +127 | 0x7F | ?         | ?         |
  | | -127 | 0x81 | ?         | ?         |
  | | -128 |    ? | 1000 0000 | ?         |
  | |   +2 |    ? | ?         | ?         |
  | |   -2 | 0xFE | ?         | ?         |
  | |   +1 | 0x01 | 0000 0001 | ?         |
  | |   -1 |    ? | 1111 1111 | ?         |
  | |    0 |    ? | ?         | ?         |
  | |------+------+-----------+-----------|
  `----


PROBLEM 3: Converting Strings to Numbers
========================================

  Inspect the program in the lab pack called `convert.c'.  Compile and
  run it using
  ,----
  | > gcc convert.c
  | > ./a.out
  `----
  Describe briefly what kind of conversion is being done by the
  `convert()' function given.
  - A. What kind of data is input?
  - B. What result is produced by the function?
  - C. How is a success versus an error reported?
  - D. Why is this kind of conversion needed?
  - E. What built-in C function (useful for the assignment) does this
    conversion function use and how is its calling convention different
    from convert()?

6 Again, What to Understand

Ensure that you understand

  • Signed vs unsigned representations
  • Two's complement representation of integers
  • Conversions between binary, decimal, octal, and hexadecimal notation

Author: Chris Kauffman (kauffman@umn.edu)
Date: 2019-09-17 Tue 20:05