Representing and manipulating information

Representing and manipulating information

:class: tip

This lecture will cover contents from Chapter 4 of the book.

How do we “see” things?

1.2 Everything is a bit

Electronic representation of bits

1.3 Encoding byte values

Hex Decimal Binary Binary to Decimal Calculation
0 0 0000 0 * $2^3$ + 0 * $2^2$ + 0 * $2^1$ + 0 * $2^0$
1 1 0001 0 * $2^3$ + 0 * $2^2$ + 0 * $2^1$ + 1 * $2^0$
2 2 0010 0 * $2^3$ + 0 * $2^2$ + 1 * $2^1$ + 0 * $2^0$
3 3 0011 0 * $2^3$ + 0 * $2^2$ + 1 * $2^1$ + 1 * $2^0$
4 4 0100 0 * $2^3$ + 1 * $2^2$ + 0 * $2^1$ + 0 * $2^0$
5 5 0101 0 * $2^3$ + 1 * $2^2$ + 0 * $2^1$ + 1 * $2^0$
6 6 0110 0 * $2^3$ + 1 * $2^2$ + 1 * $2^1$ + 0 * $2^0$
7 7 0111 0 * $2^3$ + 1 * $2^2$ + 1 * $2^1$ + 1 * $2^0$
8 8 1000 1 * $2^3$ + 0 * $2^2$ + 0 * $2^1$ + 0 * $2^0$
9 9 1001 1 * $2^3$ + 0 * $2^2$ + 0 * $2^1$ + 1 * $2^0$
A 10 1010 1 * $2^3$ + 0 * $2^2$ + 1 * $2^1$ + 0 * $2^0$
B 11 1011 1 * $2^3$ + 0 * $2^2$ + 1 * $2^1$ + 1 * $2^0$
C 12 1100 1 * $2^3$ + 1 * $2^2$ + 0 * $2^1$ + 0 * $2^0$
D 13 1101 1 * $2^3$ + 1 * $2^2$ + 0 * $2^1$ + 1 * $2^0$
E 14 1110 1 * $2^3$ + 1 * $2^2$ + 1 * $2^1$ + 0 * $2^0$
F 15 1111 1 * $2^3$ + 1 * $2^2$ + 1 * $2^1$ + 1 * $2^0$

1.4 How are data represented?

C data type typical 32-bit typical 64-bit x86_64
char 1 1 1
short 2 2 2
int 4 4 4
long 4 8 8
float 4 4 4
double 8 8 8
pointer 4 8 8

Bit-level operations in C

A B A&B A|B A^B ~A
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0
bitwise boolean operations 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

 

## Encoding integers

### 3.1 Mathematical equation

- Assumption:
  - $X$ is a decimal number
  - $X$ can be represented using $w$ bits under the form $x_{w-1}x_{w-2}...x_{i}...x_{1}x_{0}$. 
  - $x_i$ is a binary value at bit position $i$ with $0\leq i \leq (w - 1)$

- The mathematical equation governing the encoding from an unsigned value of $X$ into a 
sequence of binary values $x_{w-1}x_{w-2}...x_{i}...x_{1}x_{0}$ is:

$X=\sum_{i=0}^{w-1}x_{i}*2^{i}$

### 3.2 What about negative numbers?

- Approaches:
  - Reserve first bit as sign bit
  - One's complement: The addition of a negative number 
  and its corresponding positive value (`complement`) in 
  an `N-bit` binary representation will result in 
  a binary representation that has `N ones`. 
    - For example: in a 3-bit representation, $2$ is represented as 
    `010`, and $-2$ is represented as `101`. Then, $2+(-2)$ becomes 
    $010+101=111$.
  - Two's complement: The addition of a negative number 
  and its corresponding positive value ('complement`) in 
  an `N-bit` binary representation will a binary representation 
  of to $2^N$. 
    - For example: in a 3-bit representation, $3$ is represented as 
    `011` and $-3$ is represented as `101`. The sum of these two 
    binary representations is `1000`, which is the binary 
    representation of $2^3$. 
- Two's complement is preferred in modern computing design 
as it supports fundamental arithmetic operations of addition, 
subtraction, and multiplication of integer numbers as if these 
numbers were positive. 
- The mathematical equation governing the encoding from a signed 
value of $X$ into a 2's complement sequence of binary values 
$x_{w-1}x_{w-2}...x_{i}...x_{1}x_{0}$ is:

$X=-x_{w-1} * 2^{w-1} + \sum_{i=0}^{w-2}x_{i}*2^{i}$

- For 2’s complement, most significant bit indicates sign.
  - 0 for nonnegative
  - 1 for negative


| Unsigned | Binary | 2's complement| 1's complement | 
| -------- | ------ | ------------- | -------------- |
|     0    |  0000  |        0      |        0       |
|     1    |  0001  |        1      |        1       |
|     2    |  0010  |        2      |        2       |
|     3    |  0011  |        3      |        3       |
|     4    |  0100  |        4      |        4       |
|     5    |  0101  |        5      |        5       |
|     6    |  0110  |        6      |        6       |
|     7    |  0111  |        7      |        7       |
|     8    |  1000  |        8      |       -7       |
|     9    |  1001  |       -7      |       -6       |
|    10    |  1010  |       -6      |       -5       |
|    11    |  1011  |       -5      |       -4       |
|    12    |  1100  |       -4      |       -3       |
|    13    |  1101  |       -3      |       -2       |
|    14    |  1110  |       -2      |       -1       |
|    15    |  1111  |       -1      |        0       |

- C does not mandate using 2's complement. 
  - But, most machines do, and we will assume so. 

|             | Decimal | Hex   | Binary            |
| ----------- | ------- | ----- | ----------------- | 
| short int x | 15213   | 3B 6D | 00111011 01101101 |  
| short int y | -15213  | C4 93 | 11000100 10010011 | 


- **2's complement representation depends on the number of bits.**
- Technical trick: A binary representation of the absolute value of 
negative 2 to the power of the number of bits minus the absolute value of the
negative number. 
- Simple example for 5-bit representation

|     | -16 | 8  | 4  | 2 | 1 |                   |
| --  | --- | -- | -- | - | - | ----------------- |  
| 10  | 0   | 1  | 0  | 1 | 0 | 8 + 2 = 10        |  
| -10 | 1   | 0  | 1  | 1 | 0 | -16 + 4 + 2 = -10 |

- Simple example for 6-bit representation

|     | -32 | 16 | 8  | 4 | 2 | 1 |                        |
| --  | --- | -- | -- | - | - | - |----------------------- |  
| 10  | 0   | 0  | 1  | 0 | 1 | 0 | 8 + 2 = 10             |  
| -10 | 1   | 1  | 0  | 1 | 1 | 0 | -32 + 16 + 4 + 2 = -10 |

- Complex example

|             | Decimal | Hex   | Binary            |
| ----------- | ------- | ----- | ----------------- | 
| short int x | 15213   | 3B 6D | 00111011 01101101 |  
| short int y | -15213  | C4 93 | 11000100 10010011 |

| Weight | 15213 |       | -15213 |        |
| ------ | ----- | ----- | ------ | ------ |
| 1      | 1     | 1     | 1      | 1      |
| 2      | 0     | 0     | 1      | 2      |
| 4      | 1     | 4     | 0      | 0      |
| 8      | 1     | 8     | 0      | 0      |
| 16     | 0     | 0     | 1      | 16     |
| 32     | 1     | 32    | 0      | 0      |
| 64     | 1     | 64    | 0      | 0      |
| 128    | 0     | 0     | 1      | 128    |
| 256    | 1     | 256   | 0      | 0      |
| 512    | 1     | 512   | 0      | 0      |
| 1024   | 0     | 0     | 1      | 1024   |
| 2048   | 1     | 2048  | 0      | 0      |
| 4096   | 1     | 4096  | 0      | 0      |
| 8192   | 1     | 8192  | 0      | 0      |
| 16384  | 0     | 0     | 1      | 16384  |
| -32768 | 0     | 0     | 1      | -32768 |
| ------ | ----- | ----- | ------ | ------ |
| Sum    |       | 15213 |        | -15213 |

3.3 Numeric ranges

  8 (1 byte) 16 (2 bytes) 32 (4 bytes) 64 (8 bytes)
UMax 255 65,535 4,294,967,295 18,446,744,073,709,551,615
TMax 127 32,767 2,147,483,647 9,223,372,036,854,775,807
TMin -128 -32,768 -2,147,483,648 -9,223,372,036,854,775,808

:::{dropdown} Solution -p allows the creation of all directories on the specified path, regardless whether any directory on that path exists.

:::



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

 
## Conversions (casting)


- C allows casting between different numeric data types. 
- What should be the effect/impact?
- Notations:
  - B2T: Binary to 2's complement
  - B2U: Binary to unsigned 
  - U2B: Unsigned to binary
  - U2T: Unsigned to 2's complement
  - T2B: 2's complement to binary
  - T2U: 2's complement to unsigned



:::{image} fig/03-data-representation/data_04.png
:alt: 2's complement to unsigned
:class: bg-primary mb-1
:height: 200px
:align: center
:::

 - $T2U_{w}(x) = x + 2^{w} \ if \ x < 0$
 - $T2U_{w}(x) = x \ if \  x \geq 0$

:::{image} fig/03-data-representation/data_05.png
:alt: unsigned to 2's
:class: bg-primary mb-1
:height: 200px
:align: center
:::

 - $U2T_{w}(x) = x - 2^{w} \ if x > TMax_{w}$
 - $U2T_{w}(x) = x \ if \  x \leq TMax_{w}$

- Summary
  - Bit pattern is maintained but reinterpreted
  - Can have unexpected effects: adding or subtracting 2<sup>w</sup>
  - When expressions contain both signed and unsigned int values, int values will be casted to unsigned. 



- Create a file named `casting.c` with the following contents:

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=casting.c"></script>

- Compile and run `casting.c`.
- Confirm that converted values are correct. 



- What is wrong with the following program? 

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=for_loop.c"></script>
- How can this program be corrected?

:::{dropdown} Solution
- Change the range to 11-1
- Why don't we change the type of i?
that path exists. 
:::



- Expanding (e.g., short int to int)
  - Unsigned: zeros added
  - Signed: sign extension
  - Both yield expected result

:::{image} fig/03-data-representation/data_06.png
:alt: expanding
:class: bg-primary mb-1
:height: 200px
:align: center
:::

- Truncating (e.g., unsigned to unsigned short)
  - Unsigned/signed: bits are truncated
  - Result reinterpreted
  - Unsigned: mod operation
  - Signed: similar to mod
  - For small (in magnitude) numbers yields expected behavior

:::{image} fig/03-data-representation/data_07.png
:alt: truncating
:class: bg-primary mb-1
:height: 200px
:align: center
:::



<iframe width="560" height="315" src="https://www.youtube.com/embed/m7bv_YcZzn0" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

- [Thule Site J](https://en.wikipedia.org/wiki/Thule_Site_J): USAF radar station for
missile warning and spacecraft tracking. 
- "There are many examples of errors arising from incorrect or incomplete specifications. 
One such example is a false alert in the early days of the nuclear age, when on 
October 5, 1960, the warning system at NORAD indicated that the United States was 
under massive attack by Soviet missiles with a certainty of 99.9 percent. It turned 
out that the Ballistic Missile Early Warning System (BMEWS) radar in Thule, 
Greenland, had spotted the rising moon. Nobody had thought about the moon when specifying 
how the system should act." (Computer System Reliability and Nuclear War, CACM 1987).
- Moon's large size: 1000s of objects reported. 
- Moon's distance: .25 million miles
  - Thule's BMEWS max distance: 3000 miles. 
  - Truncated distance to the moon: `% sizeof(distance)` = 2200 miles. 
- Remember assignment 1: The computer does not "see", it only interprets.
  - **Thousands of objects on the sky within missile detection range!**. 
- Human control:
  - Kruschev was in New York on October 5, 1960. 
  - Someone at Thule said, "why not go check outside?"

Addition, multiplication, and negation (of integers)

\[\ 0010 \\ +\ 0110 \\ \hline \ 1000\] \[\ 1011 \\ +\ 1100 \\ \hline \ 10111\] \[\ 0101 \\ +\ 1001 \\ \hline \ 1110\]

$1110=(-1)(1)(8)+(1)(4)+(1)(2)+(0)*1)=(-8)+4+2=(-2)$

:::{dropdown} Solution :::



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

 
## Byte-oriented memory organization


- Programs refer to data by address
  - Conceptually, envision it as a very large array of bytes
    - In reality, it’s not, but can think of it that way
  - An address is like an index into that array
    - and, a pointer variable stores an address
- Note: system provides private address spaces to each "process"
  - Think of a process as a program being executed
  - So, a program can clobber its own data, but not that of others



- Any given computer has a "Word Size"
- `word size": Nominal size of integer-valued data and of addresses
- Until recently, most machines used 32 bits (4 bytes) as word size
  - Limits addresses to 4GB (232 bytes)
- Increasingly, machines have 64-bit word size
  - Potentially, could have 18 EB (exabytes) of addressable memory
  - That’s 18.4 X 1018
- Machines still support multiple data formats
  - Fractions or multiples of word size
  - Always integral number of bytes



- Addresses specific byte locations
  - Address of first byte in word.
  - Address of successive words differ by 4 (32-bit) or 8 (64-bit). 





<figure
  
>
  <picture>
    <!-- Auto scaling with imagemagick -->
    <!--
      See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
      https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
    -->
    
      
        <source
          class="responsive-img-srcset"
          
            srcset="/assets/img/courses/csc231/03-data-representation/data_08-480.webp 480w,/assets/img/courses/csc231/03-data-representation/data_08-800.webp 800w,/assets/img/courses/csc231/03-data-representation/data_08-1400.webp 1400w,"
            type="image/webp"
          
          
            sizes="95vw"
          
        >
      
    
    <img
      src="/assets/img/courses/csc231/03-data-representation/data_08.png"
      
      
        width="100%"
      
      
        height="auto"
      
      
        style="
          
          
          
            max-width: 50%;
          
          
        "
      
      
        alt="word-oriented memory organization"
      
      
      
        data-zoomable
      
      
        loading="lazy"
      
      onerror="this.onerror=null; $('.responsive-img-srcset').remove();"
    >
  </picture>

  
</figure>




- Machine-dependent
- Big Endian:  Sun (Oracle SPARC), PPC Mac, Internet (network data transfer)
  - Least significant byte has the highest address.
- Little Endian: x86, ARM processors running Android, iOS, and Linux
  - Least significant byte has lowest address.
- Example
  - Variable x has 4-byte value of 0x01234567
  - Address given by `&x` is 0x100

:::{image} fig/03-data-representation/data_09.png
:alt: byte ordering example
:class: bg-primary mb-1
:height: 100px
:align: center
:::



- Make sure that you are inside `03-data` directory.
- Create a file named `byte_ordering.c` with the following contents:

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=byte_ordering.c"></script>

- Compile and run `byte_ordering.c`.
- Confirm that calculated values are correct.

Fractional binary numbers (float and double)

:::{image} fig/03-data-representation/data_10.png :alt: floating encoding :class: bg-primary mb-1 :height: 100px :align: center :::

:::{image} fig/03-data-representation/data_11.png :alt: 32-bit encoding :class: bg-primary mb-1 :height: 100px :align: center :::

:::{image} fig/03-data-representation/data_12.png :alt: 64-bit encoding :class: bg-primary mb-1 :height: 100px :align: center :::



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

 

- Depends on the `exp` field (`E`).
- Denormalized: `exp` contains all 0s.
- Special: `exp` contains all 1s.
- Normalized: `exp` contains a mix of 0s and 1s. 



- When: exp != 000…0 and exp != 111…1
- Exponent coded as a biased value: E  =  exp – Bias
  - exp: unsigned value of `exp` field 
  - $Bias = 2^{k-1} - 1$, where `k` is number of exponent bits
    - Single precision: 127 (exp: 1…254, E: -126…127)
    - Double precision: 1023 (exp: 1…2046, E: -1022…1023)
- Significand coded with implied leading 1: M  =  1.xxx…x<sub>2</sub>
  - xxx…x: bits of `frac` field
  - Minimum when frac=000…0 (M = 1.0)
  - Maximum when frac=111…1 (M = 2.0 – ε)
  - Get extra leading bit for "free" (hence the range: `[1.0, 2.0)`)



- Value: float F = 15213.0;
  - 15213<sub>10</sub>= 11101101101101<sub>2</sub>= 1.1101101101101<sub>2</sub>* 2<sup>13</sup>
- Significand:
  - M = 1.1101101101101<sub>2</sub>
  - `frac` = 11011011011010000000000<sub>2</sub>
- Exponent:
  - E = 13
  - Bias = 127
  - `exp` = 140 = 10001100<sub>2</sub>
 - Result: `0`|`10001100`|`11011011011010000000000` 



- Make sure that you are inside `03-data` directory.
- Create a file named `show_fp.c` with the following contents:

<script src="https://gist.github.com/linhbngo/d1e9336a82632c528ea797210ed0f553.js?file=show_fp.c"></script>

- Compile and run `show_fp.c`.
- Confirm that calculated values in the previous example are correct. 



- Condition: exp = 000…0 
- Exponent value: E = 1 – Bias
 - Significand coded with implied leading 0: M = 0.xxx…x<sub>2</sub>
   - xxx…x: bits of frac
- Cases
  - exp = 000…0, frac = 000…0
    - Represents zero value
    - Note distinct values: +0 and –0
  - exp = 000…0, frac ≠ 000…0
    - Numbers closest to 0.0
    - Equispaced



- Condition: exp = 111...1 
- Case: exp = 111…1, frac = 000…0
  - Represents value infinity
  - Operation that overflows
  - Both positive and negative
- Case: exp = 111…1, frac != 000…0
  - Not-a-Number (NaN)
  - Represents case when no numeric value can be determined

Floating operations

  1.40 1.60 1.50 2.50 -1.50
Towards zero 1 1 1 2 -1
Round down 1 1 1 2 -2
Round up 2 1 1 3 -1
Nearest even (default) 1 2 2 2 -2

```