CMSC216 HW04: Binary Representation and Bit Operations

Homeworks are optional practice with no submission and no credit

CODE DISTRIBUTION: hw04-code.zip

Download the code distribution every lab
See further setup instructions below

CHANGELOG: Empty

1. Rationale
- Associated Reading / Preparation
- Grading Policy
2. Codepack
3. Two's Complement Arithmetic
4. Octal and Hexadecimal Representation of Numbers
5. Questions

1 Rationale

Computing deals with numbers that are written in several different forms. Most integers follow either unsigned or signed two's complement encoding formats and like most programming languages, C provides bit-level operations on those numbers. This HW provides practice on each of these topics to build fluency with bit-level representations of data.

Associated Reading / Preparation

C References: Basics of C programming including control structures, pointers/addresses, memory allocation/deallocation, bit operations
Bryant and O'Hallaron: Ch 2.1-2.3 on binary representations of integers in unsigned and two's complement signed format.

Grading Policy

Homework provides optional extra practice for students looking for it. No submission is collected and the HW is not worth any course credit. Solutions will be posted some time after the HW is posted. Students approaching course staff for additional practice problems will be asked to explain their own written answers to the QUESTIONS.txt documents in HWs before any additional problems will be constructed.

2 Codepack

The codepack for the HW contains the following files:

File	Description
`QUESTIONS.txt`	Questions to answer
`collatz.c`	Collatz Sequence calculation using bit tricks

3 Two's Complement Arithmetic

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 HW. C provides facilities to manipulate data at the bit level using logical and shift operations which are also discussed.

Understanding two's complement is necessary to complete a problem QUESTIONS.txt. The short presentation below gives the basics of two's complement but you should study the material presented in our textbook and lecture to supplement it.

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 Octal and Hexadecimal Representation of Numbers

The base-10 numbering system is taught rigorously from an early age and is familiar to most students. We have seen in the earlier Two's Complement system that numbers can also written in base-2 as Binary. This is indicative of numbers being independent of any particular notation or base. Binary is frequently used in computer science but is cumbersome as it takes a LOT of digits to write a number. When bits must be written, often they are written in a base-8 Octal format or base-16 Hexadecimal format. This is in part due to their compactness: the same bits are shown with fewer printed characters. Here is a short example.

|---------+--------------+----------------+----------------+-----------------+-----------------------|
| Decimal | Byte = 8bits | Byte by 4      | Hexadecimal    | Byte by 3       | Octal                 |
|---------+--------------+----------------+----------------+-----------------+-----------------------|
|      87 |     01010111 | bin: 0101 0111 | 57 = 5*16 + 7  | bin: 01 010 111 | 127 = 1*8^2 + 2*8 + 7 |
|         |              | hex: 5    7    | hex  dec       | oct: 1  2   7   | oct   dec             |
|         |              |                |                |                 |                       |
|      60 |     00111100 | bin: 0011 1100 | 3C = 3*16 + 12 | bin: 00 111 100 | 074 = 0*8^2 + 7*8 + 4 |
|         |              | hex: 3    C=12 | hex  dec       | oct: 0  7   4   | oct   dec             |
|         |              |                |                |                 |                       |
|     226 |     11100010 | bin: 1110 0010 | E2 = 14*16 + 2 | bin: 11 100 010 | 342 = 3*8^2 + 4*8 + 2 |
|         |              | hex: E=14 2    | hex  dec       | oct: 3  4   2   | oct   dec             |
|---------+--------------+----------------+----------------+-----------------+-----------------------|

Several items are of note:

The same number is written in 4 forms, Decimal, Binary, Hexadecimal, and Octal
A single Hexadecimal digit ranges from decimal 0-15. Values larger than 9 are written as letters: A=10, B=11, C=12, D=13, E=14, F=15
Converting between Binary and Hexadecimal is easiest when grouping bits by 4: each 4 bits corresponds to one hexadecimal digit
Octal digits ranger from 0-7
Converting between Binary and Octal is easiest when grouping bits by 3: each 3 bits corresponds to one octal digit

5 Questions

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

                           _________________

                            HW 04 QUESTIONS
                           _________________


HWs are optional practice and there is no submission.


PROBLEM 1: Number Conversions
=============================

A Unsigned Number Conversions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  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 32-bit Integer
~~~~~~~~~~~~~~~~

  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:  ??
  `----


C Signed Integer Conversions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  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.


D Signed Conversions Table
~~~~~~~~~~~~~~~~~~~~~~~~~~

  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 |    ? | ?         | ?         |
  | |------+------+-----------+-----------|
  `----


E Overall Conversion Table
~~~~~~~~~~~~~~~~~~~~~~~~~~

  Complete the following table of conversions between CS numbering
  systems. The "Signed Decimal" column presumes the Two's Complement
  convention for number representation; review this with a TA if you are
  not clear on it.

  ,----
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       | Unsigned | Signed  |
  | | Num | Binary    |  Hex | Octal |  Decimal | Decimal |
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       |          |         |
  | |   1 | 1011 1000 |      |       |      184 |         |
  | |     |           |      |       |          |         |
  | |   2 |           | 0x80 |  0200 |          | -128    |
  | |     |           |      |       |          |         |
  | |   3 | 0011 0010 | 0x32 |       |       50 |         |
  | |     |           |      |       |          |         |
  | |   4 |           |      |  0234 |      156 |         |
  | |     |           |      |       |          |         |
  | |-----+-----------+------+-------+----------+---------|
  `----


PROBLEM 2: C Bit Operations in Collatz
======================================

  Examine the program collatz.c which performs a similar computation to
  a Lab01 code except that this version uses bitwise operations in the
  function collatz_bitwise().  Examine the locations labeled with
  comments and shown below and describe the equivalent "normal"
  arithmetic that is happening at each postion.


A
~

  ,----
  |   int neg_mask = 0x1 << 31;     // A
  |   if(n & neg_mask){             // A
  |     return -1;
  |   }
  `----


B
~

  ,----
  |     if(n & 0x1){                // B
  |       ...
  |     }
  |     else{
  |       ...
  |     }
  `----


C
~

  ,----
  |       n = ((n << 2) - n) + 1;   // C
  `----


D
~

  ,----
  |       n = n >> 1;               // D
  `----