Chapter 2 - Representing and Manipulating Information Flashcards
1
Q
What is a byte?
A
The smallest unit of addressable memory.
2
Q
What base does hexadecimal use?
A
Base 16.
3
Q
Why is it useful to write bit patterns with hexadecimal rather than binary or decimal?
A
Binary can be too “verbose” and decimal makes it difficult to convert to and from bit patterns.
4
Q
If a binary number does not contain a multiple of 4 bits, how should the bits be grouped?
A
From right to left so that the leftmost group is the smallest.
5
Q
What is the hexadecimal equivalent of the following binary number?
11 1100 1010 1101 1011 0011
A
11 1100 1010 1101 1011 0011
3 C A D B 3
i.e. 0x3CADB3.
6
Q
What is the bit pattern associated with the hexadecimal representation 0x25B9D2?
A
0x25B9D2 has bit pattern:
0010 0101 1011 1001 1101 0010
7
Q
What is the hexadecimal representation for the binary pattern 1010 1110 0100 1001?
A
1010 1110 0100 1001 has hex representation 0xAE49.
8
Q
If a number has the form x=2^N, how many zeros will it contain in its bit pattern after the leading 1?
A
N zeros.
9
Q
How can a number of the form x=2^N be easily written straight into hex?
A
By determining i and j such that N=i+4j. There will be j zeros after the nonzero hex character and i determines the nonzero hex character (which is given by 2^i).
For example, 2^11 has N=3+4*2, and 2^3=8, so 2^11=0x800.
10
Q
Do the numbers below match?
N (decimal): 5
2^N (hex): 0x20.
A
Yes.
N=5=i+4j=1+4*1 (and 2^1=2), so 2^N in hex is 0x20.
11
Q
Do the numbers below match?
N (decimal): 23
2^N (hex): 0x400000.
A
No.
N=23=i+4j=3+4*5 (and 2^3=8), so 2^N in hex is 0x800000.
12
Q
Do the numbers below match?
N (decimal): 15
2^N (hex): 0x8000.
A
Yes.
N=15=i+4j=3+4*3 (and 2^3=8), so 2^N in hex is 0x8000.
13
Q
Do the numbers below match?
N (decimal): 12
2^N (hex): 0x1000.
A
Yes.
N=12=i+4j=0+4*3 (and 2^0=1), so 2^N in hex is 0x1000.
14
Q
Do the numbers below match?
Binary: 1001 1110
Hex: 0x9E
A
Yes.
15
Q
Do the numbers below match?
Binary: 1001 0001
Hex: 0x91
A
Yes.
16
Q
Do the numbers below match?
Binary: 1010 1110
Hex: 0xAE
A
Yes.
17
Q
Do the numbers below match?
Binary: 0111 0101
Hex: 0x73
A
No.
18
Q
Is the following correct?
0x605C + 0x5 = 0x606A
A
No. 0x605C + 0x5 = 0x6061.
19
Q
Is the following correct?
0x605C + 32 = 0x607C
A
Yes. 0x605C + 0x20 = 0x607C.
20
Q
What is the result of the expression?
0x60FA - 0x605C = ???
A
0x60FA - 0x605C = 0x9D.
21
Q
What important system parameter indicates the nominal size of pointer data?
A
The word size.
22
Q
What is the size of the virtual address space of a machine with a w-bit word size?
A
The machine can access address 0 to 2^w-1 so there are 2^w addressable bytes.
23
Q
What is the virtual address space limit of a machine with a 32-bit word size?
A
4GB.
24
Q
True or false? 64-bit machines can run 32-bit programs.
A
True.
25
How can the program prog.c be compiled with gcc so that it runs on both 32-bit and 64-bit machines?
With the command:
| $ gcc -m32 prog.c
26
Can the program resulting from the command
$ gcc -m64 prog.c
be run on a 32-bit machine?
No. It has been compiled as a 64-bit program so it can only run on a 64-bit machine.
27
What size will a pointer used in the program prog.c, compiled as below have?
$ gcc -m32 prog.c
A pointer uses the full word size of the program so the pointer will be 4 bytes in size.
28
What is the term used to describe a system where the bytes are ordered from least significant to most significant?
Little endian.
29
What is the term used to describe a system where the bytes are ordered from most significant to least significant?
Big endian.
30
Can a system be configured as little endian or big endian?
Typically, no, but more recent microprocessor chips are "bi-endian" and can be configured as either.
31
Where do the terms little and big endian come from?
From Gullivers Travels by Jonathan Swift, where two warring factions could not settle on how a hard-boiled egg should be open -- by the little end or the big.
32
When might the ordering of bytes become important? (i.e. the little- or big-endian-ness.)
In the communication of binary data over a network between different machines.
33
What would the outputs of the following code be on a little endian machine?
int a=0x12345678;
unsigned char* ap=(unsigned char*) &a;
show_bytes(ap,1);
show_bytes(ap,2);
show_bytes(ap,3);
Here, show_bytes(p,N) is a function that prints the first N bytes at a given location.
```
int a=0x12345678;
unsigned char* ap=(unsigned char*) &a;
show_bytes(ap,1); // = 78
show_bytes(ap,2); // = 78 56
show_bytes(ap,3); // = 78 56 34
```
34
What would the outputs of the following code be on a big endian machine?
int a=0x12345678;
unsigned char* ap=(unsigned char*) &a;
show_bytes(ap,1);
show_bytes(ap,2);
show_bytes(ap,3);
Here, show_bytes(p,N) is a function that prints the first N bytes at a given location.
```
int a=0x12345678;
unsigned char* ap=(unsigned char*) &a;
show_bytes(ap,1); // = 12
show_bytes(ap,2); // = 12 34
show_bytes(ap,3); // = 12 34 56
```
35
What is the hex code for the decimal digit 1 in ASCII? What would the byte representation of "12345" look like in memory?
The ASCII code for the decimal digit 1 is 31 in hex. Thus, "12345" is given by 31 32 33 34 35.
36
True or false? Text data is more platform independent than binary data.
True.
37
What would be printed as a result of the following call to show_bytes?
const char *m = "mnopqr";
show_bytes((unsigned char*) m, strlen(m));
Note that letters ‘a’ through ‘z’ have ASCII codes 0x61 through 0x7A.
```
const char *m = "mnopqr";
show_bytes((unsigned char*) m, strlen(m));
// Note: m is the 13th letter so it starts with 0x60+0xD=0x6D.
// The full sequence of bytes is 6D 6E 6F 70 71 72.
```
38
What are the symbols uses to denote Boolean algebra operations?
NOT: ~
AND: &
OR: |
EXCLUSIVE-OR: ^
39
Suppose a=[01001110] and b=[11100001]. What is "a^b"?
The character ^ is used to denote the exclusive-or operation so, given a=[01001110] and b=[11100001], a^b=[10101111].
40
What term is used to describe the operation where one bit pattern is used to select bits from another bit pattern?
Bit masking.
41
Write C expressions, in terms of variable x, for the following values. The code should work for any word size w ≥ 8. For reference, the result of evaluating the expressions for x = 0x87654321, with w = 32, is shown.
A. The least significant byte of x, with all other bits set to 0. [0x00000021]
B. All but the least significant byte of x complemented, with the least significant byte left unchanged. [0x789ABC21]
C. The least significant byte set to all ones, and all other bytes of x left unchanged.
[0x876543FF]
Reference: x = 0x87654321.
A. x & 0xFF [0x00000021]
B. x ^ (~0xFF) [0x789ABC21]
C. x | 0xFF [0x876543FF]
42
What is a simple way to multiply a variable x by 2^N?
By using the bit shift x<
43
Do bit shift operations associate left to right or right to left? For example, what is the order of operations in the expression x << j << k?
Bit shift operations associate left to right so x << j << k is equivalent to (x << j) << k.
44
Using only bit-level and logical operations, write a C expression that is equivalent to x == y. In other words, it will return 1 when x and y are equal and 0 otherwise.
(x^y) will have entry 1 wherever x and y differ and entry 0 wherever x and y are the same. Thus, x == y can be represented by the expression !(x^y).
45
What two types of right shift are there?
Logical and arithmetic.
46
What effect does a logical right shift x>>k have on the bit pattern x?
The logical right shift x>>k fills the left end of x with k zeros.
47
What effect does an arithmetic right shift x>>k have on the bit pattern x?
The logical right shift x>>k fills the left end of x with k repetitions of the most significant bit of x.
48
What data types are logical and arithmetic right shifts used on?
Logical right shifts are used on unsigned integer data and arithmetic right shifts are used on signed integer data.
49
Suppose x=[01100011]. What are the results of the following operations?
1. x << 4
2. x >> 4 (logical)
3. x >> 4 (arithmetic)
x=[01100011].
1. x << 4 gives [00110000]
2. x >> 4 (logical) gives [00000110]
3. x >> 4 (arithmetic) gives [00000110]
50
Suppose x=[10010101]. What is the result of the following operations?
1. x << 4
2. x >> 4 (logical)
3. x >> 4 (arithmetic)
x=[10010101].
1. x << 4 gives [01010000]
2. x >> 4 (logical) gives [00001001]
3. x >> 4 (arithmetic) gives [11111001]
51
What is the maximum unsigned integer value on a w-bit machine?
UMax_w=2^w - 1.
52
What are the minimum and maximum signed integer values on a w-bit machine?
```
TMax = 2^{w-1}-1.
TMin = -2^{w-1}.
```
53
What encoding is typically used to represent signed integers?
Two's complement.
54
Apart from two's complement, what are two other types of encoding for signed integers?
One's complement and sign magnitude.
55
Let TMin and TMax be the min. and max. values of two's complement integers, respectively. What is the relationship between TMin and TMax?
|TMin| = |TMax| +1.
56
Let UMax and TMax be the max. values of two's complement and unsigned integers, respectively. What is the relationship between UMax and TMax?
UMax=2TMax+1.
57
Define the function T2U_w(x) that converts a w-bit two's complement integer to an unsigned integer.
Let y=T2U_w(x), then:
w<0: y = x + 2^w,
w>=0: y = x.
58
Define the function U2T_w(x) that converts a w-bit two's complement integer to an unsigned integer.
Let y=U2T_w(x), and let TMax be maximum two's complement integer, then:
w<=TMax: y = x,
w>TMax: y = x - 2^w.
59
Let T2U_w(x) be the function that converts a w-bit two's complement integer to an unsigned integer. What is the value of T2U_w(-1)?
T2U_w(-1) = -1 + 2^w = UMax, i.e. the maximum unsigned integer.
60
When executing a 32-bit program on a machine that uses two’s-complement arithmetic, what is the type (i.e. signed or unsigned) and value of the following expression?
-2147483647-1 == 2147483648U
(Note that TMax=2147483647.)
-2147483647-1 == 2147483648U.
(Note that TMax=2147483647.)
Type: Unsigned
Value: True, as U2T_32(-2147483647-1) = TMax+1.
61
When executing a 32-bit program on a machine that uses two’s-complement arithmetic, what is the type (i.e. signed or unsigned) and value of the following expression?
-2147483647-1 < 2147483647
(Note that TMax=2147483647.)
-2147483647-1 < 2147483647.
(Note that TMax=2147483647.)
Type: Signed
Value: True, as -2147483647-1 = TMin.
62
When executing a 32-bit program on a machine that uses two’s-complement arithmetic, what is the type (i.e. signed or unsigned) and value of the following expression?
-2147483647-1U < 2147483647
(Note that TMax=2147483647.)
-2147483647-1U < 2147483647.
(Note that TMax=2147483647.)
Type: Unsigned
Value: False, as U2T_32(-2147483647-1) = TMax+1.
63
When executing a 32-bit program on a machine that uses two’s-complement arithmetic, what is the type (i.e. signed or unsigned) and value of the following expression?
-2147483647-1 < -2147483647
(Note that TMax=2147483647.)
-2147483647-1 < -2147483647.
(Note that TMax=2147483647.)
Type: Signed
Value: True, as -2147483647-1 = TMin, and -2147483647 = = TMin+1.
64
When executing a 32-bit program on a machine that uses two’s-complement arithmetic, what is the type (i.e. signed or unsigned) and value of the following expression?
-2147483647-1U < -2147483647
(Note that TMax=2147483647.)
-2147483647-1U < -2147483647.
(Note that TMax=2147483647.)
Type: Unsigned
Value: True, as the relative ordering of negative integers is preserved when converting from signed to unsigned.
65
True or false? The conversion between a signed and unsigned integer is based on a numeric perspective rather than a bit-level one.
False, conversion is based on the bit-level perspective.
66
You are given the following definitions:
short sx = -12345; /* -12345 */
unsigned short usx = sx; /* 53191 */
int x = sx; /* -12345 */
unsigned ux = usx; /* 53191 */
Fill in the blanks below which give the byte representation of each of the above variables
```
sx = -12345: cf c7
usx = 53191: _________
x = -12345: _________
ux = 53191: _________
```
short sx = -12345; /* -12345 */
unsigned short usx = sx; /* 53191 */
int x = sx; /* -12345 */
unsigned ux = usx; /* 53191 */
sx = -12345: cf c7
usx = 53191: cf c7
// A signed unsigned conversion preserves the byte representation.
x = -12345: ff ff cf c7
// Expansion of a signed integer is found by sign extension.
ux = 53191: 00 00 cf c7
// Expansion of an unsigned integer is performed by zero extension.
67
What is zero extension?
Zero extension is used to extend an unsigned integer to a larger data type.
This operation involves adding leading zeros to the bit representation.
68
What is sign extension?
Signed extension is used to extend a signed integer to a larger data type.
This operation involves adding copies of the most significant bit to the representation as leading bits.
69
```
Suppose sx is defined as:
short sx = -12345;
Which of the following two is true?
(unsigned) sx <==> (unsigned) (int) sx
or
(unsigned) sx <==> (unsigned) (unsigned short) sx
```
short sx = -12345;
When converting from short to unsigned, the program first changes the size and then the type. Thus, the correct statement is:
(unsigned) sx <==> (unsigned) (int) sx
70
```
Consider the following C functions:
int fun(unsigned word)
{
return (int) ((word << 24) >> 24);
}
```
(A) What is the result of applying the above function to the following inputs?
(i) 0x00000076
(ii) 0x87654321
(iii) 0x000000C9
(iv) 0xEDCBA987
(B) Describe in words the useful computation this function performs.
```
int fun(unsigned word)
{
return (int) ((word << 24) >> 24);
}
```
(A)
(i) 0x00000076 --> 0x00000076
(ii) 0x87654321 --> 0x00000021
(iii) 0x000000C9 --> 0x000000C9
(iv) 0xEDCBA987 --> 0x00000087
(B) This function returns the number modulo 256.
71
```
Consider the following C function:
int fun(unsigned word)
{
return ((int) word << 24) >> 24;
}
```
(A) What is the result of applying the above function to the following inputs?
(i) 0x00000076
(ii) 0x87654321
(iii) 0x000000C9
(iv) 0xEDCBA987
(B) Describe in words the useful computation this function performs.
```
int fun(unsigned word)
{
return ((int) word << 24) >> 24;
}
```
(A)
(i) 0x00000076 --> 0x00000076
(ii) 0x87654321 --> 0x00000021
(iii) 0x000000C9 --> 0xFFFFFFC9
(iv) 0xEDCBA987 --> 0xFFFFFF87
(B) This function returns the number modulo 256 then converts it to a two's complement integer.
72
```
/* WARNING: This is buggy code */
float sum_elements(float a[], unsigned length) {
int i;
float result = 0;
for (i = 0; i <= length-1; i++)
{
result += a[i];
return result;
}
When run with argument length equal to 0, this code should return 0.0. Instead, it encounters a memory error. Explain why this happens.
```
```
/* WARNING: This is buggy code */
float sum_elements(float a[], unsigned length) {
int i;
float result = 0;
for (i = 0; i <= length-1; i++)
// When length=0 is passed in, length-1 will become UMax and so the loop will be run 2^32-1 times.
{
result += a[i];
return result;
}
```
73
You are given the assignment of writing a function that determines whether one string is longer than another. You decide to make use of the string library function strlen having the following declaration:
```
/* Prototype for library function strlen */
size_t strlen(const char *s);
```
Here is your first attempt at the function:
```
/* Determine whether string s is longer than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, char *t) {
return strlen(s) - strlen(t) > 0;
}
```
When you test this on some sample data, things do not seem to work quite right. You investigate further and determine that, when compiled as a 32-bit program, data type size_t is defined (via typedef) in header file stdio.h to be unsigned.
(A) For what cases will this function produce an incorrect result?
(B) Explain how this incorrect result comes about.
(C) Show how to fix the code so that it will work reliably.
```
/* Prototype for library function strlen */
size_t strlen(const char *s);
```
```
/* Determine whether string s is longer than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, char *t) {
return strlen(s) - strlen(t) > 0;
}
```
(A) For what cases will this function produce an incorrect result?
// The function will incorrectly return 1 when s is shorter than t.
(B) Explain how this incorrect result comes about.
// Since strlen is defined to yield an unsigned result, the difference and the comparison are both computed using unsigned arithmetic. When s is shorter than t, the difference strlen(s) - strlen(t) should be negative, but instead becomes a large, unsigned number, which is greater than 0.
(C) Show how to fix the code so that it will work reliably.
// By changing "return strlen(s) - strlen(t) > 0;" to "return strlen(s) > strlen(t);"
74
Suppose we truncate a 4-bit value (represented by hex digits 0 through F) to a 3-bit value (represented as hex digits 0 through 7). What is the unsigned and two's complement value of the hex value "C" after truncation?
Original: C [1100]
Truncated: 4 [100]
Unsigned: 4
Two's complement: -4
75
Suppose we truncate a 4-bit value (represented by hex digits 0 through F) to a 3-bit value (represented as hex digits 0 through 7). What is the unsigned and two's complement value of the hex value "E" after truncation?
Original: C [1110]
Truncated: 4 [110]
Unsigned: 6
Two's complement: -2
76
Suppose x and y are two unsigned integers. Assuming their sum overflows, what is the result of their sum calculated?
Addition of w-bit unsigned numbers is defined as:
x+y<=UMax_w: x+y (normal)
x+y>UMax_w: x+y-2^w (overflow)
77
Suppose x and y are two unsigned integers, and their sum overflows. How can this overflow be detected?
Let s=x+y. Overflow occurs iff s= x. On the other hand, if s did overflow, we have s = x + y − 2^w. Given that y < 2^w,
we have y − 2^w < 0, and hence s = x + (y − 2^w) < x.
78
Suppose x and y are two two's complement integers. Assuming their sum overflows, what is the result of their sum calculated?
Addition of w-bit two's complement integers is defined as:
x+y>TMax_w: x+y-2^w (positive overflow)
TMin_w<=x+y<=TMax_w: x+y (normal)
x+y
79
Suppose x and y are two two's complement integers, and their sum overflows. How can this overflow be detected?
Let s=x+y, then:
x>0, y>0: Positive overflow occurs iff s<=0;
x<0, y<0: Negative overflow occurs iff s>=0;
Otherwise: overflow cannot occur.
80
How can the negation of the two's complement integers, x, be calculated at the bit level?
As follows:
| -x = ~x+1
81
True or false? Unsigned integer multiplication and two's complement integer multiplication at the bit level is equivalent.
True.
82
Suppose x and y are two's complement integers, and their product overflows. How can this overflow be detected?
Let p=x*y, then overflow occurs if x is not equal to zero and p/x is not equal to y. As code:
int p=x*y;
return (x!=0) && (p/x!=y));
83
How can the multiplication of an integer x by the k-th power of 2 be calculated using a bit operation?
With the code: x<
84
Given an number integer x. How can the multiplication x*7 be calculated using bit shifts and addition (not subtraction!)?
First note that the bit pattern of 7 is [111]. Thus:
| x*7 = (x<<2) + (x<<1) + x
85
Given an number integer x. How can the multiplication x*7 be calculated using bit shifts and subtraction (not addition!)?
First note that the bit pattern of 7 is [111]. Thus:
| x*7 = (x<<3) - x
86
True or false? Integer division always rounds toward negative infinity.
False. It round towards zero.
87
How can the division of an unsigned integer, x, by the k-th power of 2 be calculated using bit shifts?
By applying a logical right-shift to x. Given by the code:
x>>k
This automatically rounds the result towards zero.
88
How can the division of a two's complement integer, x, by the k-th power of 2 be calculated using bit shifts?
By applying a logical right-shifts to x, however, we also need to be careful to round towards zero. For x>0, this is simple. For x<0 this is more complicated and requires the introduction of a bias. In code we have:
return (x>0 ? x : (x + (1<> k;
This ensuring the result is rounded towards zero.
89
Assume an int is 32 bits long and uses a two's complement representation, and suppose you are given an int x. Will the following expression always be true? If not, give an example for which the expression is false.
(x > 0) || (x-1 < 0)
False, x=TMin.
90
Assume an int is 32 bits long and uses a two's complement representation, and suppose you are given an int x. Will the following expression always be true? If not, give an example for which the expression is false.
((x & 7) != 7) || (x<<29 < 0)
True, if (x & 7) != 7 evaluates to 0, then the three least significant bits will be equal to 1. When shifted left by 29, the sign bit will become 1.
91
Assume an int is 32 bits long and uses a two's complement representation, and suppose you are given an int x. Will the following expression always be true? If not, give an example for which the expression is false.
(x * x) >= 0
False, any integer x for which x*x is large enough to cause positive overflow will ensure that the result of x*x is a negative integer.
92
Assume an int is 32 bits long and uses a two's complement representation, and suppose you are given an int x. Will the following expression always be true? If not, give an example for which the expression is false.
(x < 0) || (-x <= 0)
True. If x is nonnegative, then -x is nonpositive.
93
Assume an int is 32 bits long and uses a two's complement representation, and suppose you are given an int x. Will the following expression always be true? If not, give an example for which the expression is false.
(x > 0) || (-x >= 0)
False. Let x be −2,147,483,648 (TMin32). Then both x and -x are negative.
94
Assume int is 32 bits long and uses a two's complement representation. Given the code:
int x = foo(); /* Assign an arbitrary value */
int y = bar(); /* Assign an arbitrary value */
unsigned ux = x;
unsigned uy = y;
Will the following expression always be true? If not, give an example for which the expression is false.
x+y == uy+ux
True. Two’s-complement and unsigned addition have the same bit-level behavior, and they are commutative, and a two's complement integer will be converted to an unsigned integer in the comparison.
95
Assume int is 32 bits long and uses a two's complement representation. Given the code:
int x = foo(); /* Assign an arbitrary value */
int y = bar(); /* Assign an arbitrary value */
unsigned ux = x;
unsigned uy = y;
Will the following expression always be true? If not, give an example for which the expression is false.
x*(~y) + uy*ux == -x
True. ~y equals -y-1. uy*ux equals x*y. Thus, the left-hand side is equivalent to (x*(-y))-x+x*y (with all of the numbers converted to unsigned integers).
96
What is the general form of an IEEE floating-point number?
V=(-1)^s * 2^E * M, where s is the sign, E is the exponent and M is the significand, or mantissa.
97
How the bits in a "double" shared in the representation of the terms in V=(-1)^s * 2^E * M.
A double uses a 64-bit representation. 1 bit is used to represent the sign, 11 bits are used to represent the exponent and 52 bits are used to represent the significand.
98
The value encoded by a given bit representation of an IEEE floating-point number can be divided into three cases. What are they?
1. Normalised numbers.
2. Denormalised numbers.
3. Special values (infinity and NaN).
99
What are two purposes of using denormalised values?
1. To provide a way to represent the value 0, and;
| 2. To provide a property called gradual underflow, where possible numeric values near 0.0 are spaced evenly.
100
An IEEE floating-point number has the representation V=(-1)^s * 2^E * M. Assume the result encoded is a normalised value. Describe how the bits of a 64-bit double are used to calculate E and M.
The k=11 bits after the sign bit are used to represent the number e, and are used to calculate E with E=e-Bias, where Bias=2^{k-1}.
The n=52 bits after the sign and number e are used to represent the fraction f. The significand M satisfies M=1+f.
101
An IEEE floating-point number has the representation V=(-1)^s * 2^E * M. The significand M satisfies M=1+f, where the fraction, f, is represented using the n=52 bits after the sign and number e. What is the term given to this representation of M?
The "implied leading 1" representation.
102
What are the conditions necessary for the value encoded by an IEEE floating-point number to be a normalised value?
At least one, but not all, of the k=11 bits after the sign bit (used to represent the exponent) must be equal to one.
103
An IEEE floating-point number has the representation V=(-1)^s * 2^E * M. Assume the result encoded is a normalised value. Describe how the bits of a 64-bit double are used to calculate E and M.
The k=11 bits after the sign bit are used to represent the number e, and are used to calculate E as E=e-Bias, where Bias=2^{k-1}.
The n=52 bits after the sign and number e are used to represent the fraction f. The significand M satisfies M=1+f.
104
What are the conditions necessary for the value encoded by an IEEE floating-point number to be a denormalised value?
Each of the k=11 bits after the sign bit (used to represent the exponent) must be equal to zero.
105
An IEEE floating-point number has the representation V=(-1)^s * 2^E * M. Assume the result encoded is a denormalised value. Describe how the bits of a 64-bit double are used to calculate E and M.
The k=11 bits after the sign bit will all be zero, and the exponent, E, will be calculated as E=1-Bias, where Bias=2^{k-1}-1.
The n=52 bits after the sign and number e are used to represent the fraction f. The significand M satisfies M=f.
106
What are the conditions necessary for the value encoded by an IEEE floating-point number to be a "special" value?
Each of the k=11 bits after the sign bit (used to represent the exponent) must be equal to one.
107
How does an IEEE floating-point number represent an infinity?
All of the k=11 bits after the sign bit must be set to 1 and all of the n=52 bits after that must be equal to zero. The sign bit can be 1 or 0 to represent negative or positive infinity, respectively.
108
How does an IEEE floating-point number represent NaN?
All of the k=11 bits after the sign bit must be set to 1 and at least one of the n=52 bits after that must be equal to one.
109
Does an IEEE floating-point number have a symmetric range of values?
Yes.
110
As mentioned in Problem 2.6, the integer 3,510,593 has hexadecimal representation 0x00359141, while the single-precision floating-point number 3,510,593.0 has hexadecimal representation 0x4A564504. Derive this floating-point representation and explain the correlation between the bits of the integer and floating-point representations.
The integer 3,510,593 has hex representation 0x00359141 = [0000 0000 0011 0101 1001 0001 0100 0001] so 3,510,593 = 1.101011001000101000001_2 x 2^21, i.e. E=21. Here, the 21 bits after the binary point represent the fraction and the bit before the binary point is the implied leading 1. A single-precision floating-point reserves k=8 bits for the exponent so the Bias is 2^7-1=127. Thus, e=E+Bias=21+127=148=128+16+4=[1001 0100] and the floating-point number 3,510,593.0 has bit representation
[0100 1010 0101 0110 0100 0101 0000 0100] = 0x4A564504, as required.
The high-order 21 bits of the fraction will match the 21 low-order bits in the integer representation of 3,510,593.
111
For a floating-point format with an n-bit fraction, give a formula for the smallest positive integer that cannot be represented exactly (because it would require an (n + 1)-bit fraction to be exact). Assume the exponent field size k is large enough that the range of representable exponents does not provide a limitation for this problem.
N=2^{n+1}+1.
The fractional bit represents the number 1.f_{n-1}...f_{0} x 2^n, which can represent a number as large as 2^{n+1}-1. The number N=2^{n+1} can be represented as the least significant bit will be 0 and can be absorbed into the exponent. The loss of accuracy is encountered for N=2^{n+1}+1.
112
True or false? Floating-point addition and multiplication are commutative and associative.
False. Floating-point addition and multiplication are commutative but not associative.
113
```
Assume variables x, f, and d are of type int, float, and double, respectively. Their values are arbitrary, except that neither f nor d equals positive infinity, negative infinity, or NaN. For each of the following C expressions, either argue that it will always be true (i.e., evaluate to 1) or give a value for the variables such that it is not true (i.e., evaluates to 0).
(A) x == (int)(double) x
(B) x == (int)(float) x
(C) d == (double)(float) d
(D) f == (float)(double) f
```
```
(A) x == (int)(double) x
// Yes, since double has greater precision and range than int.
(B) x == (int)(float) x
// No. For example, when x is TMax.
(C) d == (double)(float) d
// No. For example, when d is 1e40, we will get positive infinity on the right.
(D) f == (float)(double) f
// Yes, since double has greater precision and range than float.
```
114
```
Assume variables x, f, and d are of type int, float, and double, respectively. Their values are arbitrary, except that neither f nor d equals positive infinity, negative infinity, or NaN. For each of the following C expressions, either argue that it will always be true (i.e., evaluate to 1) or give a value for the variables such that it is not true (i.e., evaluates to 0).
(A) f == -(-f)
(B) 1.0/2 == 1/2.0
(C) d*d >= 0.0
(D) (f+d)-f == d
```
(A) f == -(-f)
// Yes, since a floating-point number is negated by simply inverting its sign bit.
(B) 1.0/2 == 1/2.0
// Yes, the numerators and denominators will both be converted to floating-point representations before the division is performed.
(C) d*d >= 0.0
// Yes, although it may overflow to positive infinity.
(D) (f+d)-f == d
// No. For example, when f is 1.0e20 and d is 1.0, the expression f+d will be rounded to 1.0e20, and so the expression on the left-hand side will evaluate to 0.0, while the right-hand side will be 1.0.
