Chapter 2 - Representing and Manipulating Information

Question 1

What is a byte?

Answer 1

The smallest unit of addressable memory.

Question 2

What base does hexadecimal use?

Answer 2

Base 16.

Question 3

Why is it useful to write bit patterns with hexadecimal rather than binary or decimal?

Answer 3

Binary can be too “verbose” and decimal makes it difficult to convert to and from bit patterns.

Question 4

If a binary number does not contain a multiple of 4 bits, how should the bits be grouped?

Answer 4

From right to left so that the leftmost group is the smallest.

Question 5

What is the hexadecimal equivalent of the following binary number?
11 1100 1010 1101 1011 0011

Answer 5

11 1100 1010 1101 1011 0011
3 C A D B 3
i.e. 0x3CADB3.

Question 6

What is the bit pattern associated with the hexadecimal representation 0x25B9D2?

Answer 6

0x25B9D2 has bit pattern:

0010 0101 1011 1001 1101 0010

Question 7

What is the hexadecimal representation for the binary pattern 1010 1110 0100 1001?

Answer 7

1010 1110 0100 1001 has hex representation 0xAE49.

Question 8

If a number has the form x=2^N, how many zeros will it contain in its bit pattern after the leading 1?

Answer 8

N zeros.

Question 9

How can a number of the form x=2^N be easily written straight into hex?

Answer 9

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.

Question 10

Do the numbers below match?
N (decimal): 5
2^N (hex): 0x20.

Answer 10

Yes.

N=5=i+4j=1+4*1 (and 2^1=2), so 2^N in hex is 0x20.

Question 11

Do the numbers below match?
N (decimal): 23
2^N (hex): 0x400000.

Answer 11

No.

N=23=i+4j=3+4*5 (and 2^3=8), so 2^N in hex is 0x800000.

Question 12

Do the numbers below match?
N (decimal): 15
2^N (hex): 0x8000.

Answer 12

Yes.

N=15=i+4j=3+4*3 (and 2^3=8), so 2^N in hex is 0x8000.

Question 13

Do the numbers below match?
N (decimal): 12
2^N (hex): 0x1000.

Answer 13

Yes.

N=12=i+4j=0+4*3 (and 2^0=1), so 2^N in hex is 0x1000.

Question 14

Do the numbers below match?
Binary: 1001 1110
Hex: 0x9E

Answer 14

Yes.

Question 15

Do the numbers below match?
Binary: 1001 0001
Hex: 0x91

Answer 15

Yes.

Question 16

Do the numbers below match?
Binary: 1010 1110
Hex: 0xAE

Answer 16

Yes.

Question 17

Do the numbers below match?
Binary: 0111 0101
Hex: 0x73

Answer 17

No.

Question 18

Is the following correct?

0x605C + 0x5 = 0x606A

Answer 18

No. 0x605C + 0x5 = 0x6061.

Question 19

Is the following correct?

0x605C + 32 = 0x607C

Answer 19

Yes. 0x605C + 0x20 = 0x607C.

Question 20

What is the result of the expression?

0x60FA - 0x605C = ???

Answer 20

0x60FA - 0x605C = 0x9D.

Question 21

What important system parameter indicates the nominal size of pointer data?

Answer 21

The word size.

Question 22

What is the size of the virtual address space of a machine with a w-bit word size?

Answer 22

The machine can access address 0 to 2^w-1 so there are 2^w addressable bytes.

Question 23

What is the virtual address space limit of a machine with a 32-bit word size?

Answer 23

4GB.

Question 24

True or false? 64-bit machines can run 32-bit programs.

Answer 24

True.

Question 25

How can the program prog.c be compiled with gcc so that it runs on both 32-bit and 64-bit machines?

Answer 25

With the command:

$ gcc -m32 prog.c

Question 26

Can the program resulting from the command
$ gcc -m64 prog.c
be run on a 32-bit machine?

Answer 26

No. It has been compiled as a 64-bit program so it can only run on a 64-bit machine.

Question 27

What size will a pointer used in the program prog.c, compiled as below have?
$ gcc -m32 prog.c

Answer 27

A pointer uses the full word size of the program so the pointer will be 4 bytes in size.

Question 28

What is the term used to describe a system where the bytes are ordered from least significant to most significant?

Answer 28

Little endian.

Question 29

What is the term used to describe a system where the bytes are ordered from most significant to least significant?

Answer 29

Big endian.

Question 30

Can a system be configured as little endian or big endian?

Answer 30

Typically, no, but more recent microprocessor chips are “bi-endian” and can be configured as either.

Question 31

Where do the terms little and big endian come from?

Answer 31

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.

Question 32

When might the ordering of bytes become important? (i.e. the little- or big-endian-ness.)

Answer 32

In the communication of binary data over a network between different machines.

Question 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.

Answer 33

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

Question 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.

Answer 34

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

Question 35

What is the hex code for the decimal digit 1 in ASCII? What would the byte representation of “12345” look like in memory?

Answer 35

The ASCII code for the decimal digit 1 is 31 in hex. Thus, “12345” is given by 31 32 33 34 35.

Question 36

True or false? Text data is more platform independent than binary data.

Answer 36

True.

Question 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.

Answer 37

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.

Question 38

What are the symbols uses to denote Boolean algebra operations?

Answer 38

NOT: ~
AND: &
OR: |
EXCLUSIVE-OR: ^

Question 39

Suppose a=[01001110] and b=[11100001]. What is “a^b”?

Answer 39

The character ^ is used to denote the exclusive-or operation so, given a=[01001110] and b=[11100001], a^b=[10101111].

Question 40

What term is used to describe the operation where one bit pattern is used to select bits from another bit pattern?

Answer 40

Bit masking.

Question 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]

Answer 41

Reference: x = 0x87654321.
A. x & 0xFF [0x00000021]
B. x ^ (~0xFF) [0x789ABC21]
C. x | 0xFF [0x876543FF]

Question 42

What is a simple way to multiply a variable x by 2^N?

Answer 42

By using the bit shift x<

Question 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 &laquo_space;j &laquo_space;k?

Answer 43

Bit shift operations associate left to right so x &laquo_space;j &laquo_space;k is equivalent to (x &laquo_space;j) &laquo_space;k.

Question 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.

Answer 44

(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).

Question 45

What two types of right shift are there?

Answer 45

Logical and arithmetic.

Question 46

What effect does a logical right shift x»k have on the bit pattern x?

Answer 46

The logical right shift x»k fills the left end of x with k zeros.

Question 47

What effect does an arithmetic right shift x»k have on the bit pattern x?

Answer 47

The logical right shift x»k fills the left end of x with k repetitions of the most significant bit of x.

Question 48

What data types are logical and arithmetic right shifts used on?

Answer 48

Logical right shifts are used on unsigned integer data and arithmetic right shifts are used on signed integer data.

Question 49

Suppose x=[01100011]. What are the results of the following operations?

1. x &laquo_space;4
2. x&raquo_space; 4 (logical)
3. x&raquo_space; 4 (arithmetic)

Answer 49

x=[01100011].

1. x &laquo_space;4 gives [00110000]
2. x&raquo_space; 4 (logical) gives [00000110]
3. x&raquo_space; 4 (arithmetic) gives [00000110]

Question 50

Suppose x=[10010101]. What is the result of the following operations?

1. x &laquo_space;4
2. x&raquo_space; 4 (logical)
3. x&raquo_space; 4 (arithmetic)

Answer 50

x=[10010101].

1. x &laquo_space;4 gives [01010000]
2. x&raquo_space; 4 (logical) gives [00001001]
3. x&raquo_space; 4 (arithmetic) gives [11111001]

Question 51

What is the maximum unsigned integer value on a w-bit machine?

Answer 51

UMax_w=2^w - 1.

Question 52

What are the minimum and maximum signed integer values on a w-bit machine?

Answer 52

TMax = 2^{w-1}-1.
TMin = -2^{w-1}.

Question 53

What encoding is typically used to represent signed integers?

Answer 53

Two’s complement.

Question 54

Apart from two’s complement, what are two other types of encoding for signed integers?

Answer 54

One’s complement and sign magnitude.

Question 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?

Answer 55

|TMin| = |TMax| +1.

Question 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?

Answer 56

UMax=2TMax+1.

Question 57

Define the function T2U_w(x) that converts a w-bit two’s complement integer to an unsigned integer.

Answer 57

Let y=T2U_w(x), then:
w<0: y = x + 2^w,
w>=0: y = x.

Question 58

Define the function U2T_w(x) that converts a w-bit two’s complement integer to an unsigned integer.

Answer 58

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.

Question 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)?

Answer 59

T2U_w(-1) = -1 + 2^w = UMax, i.e. the maximum unsigned integer.

Question 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.)

Answer 60

-2147483647-1 == 2147483648U.
(Note that TMax=2147483647.)
Type: Unsigned
Value: True, as U2T_32(-2147483647-1) = TMax+1.

Question 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.)

Answer 61

-2147483647-1 < 2147483647.
(Note that TMax=2147483647.)
Type: Signed
Value: True, as -2147483647-1 = TMin.

Question 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.)

Answer 62

-2147483647-1U < 2147483647.
(Note that TMax=2147483647.)
Type: Unsigned
Value: False, as U2T_32(-2147483647-1) = TMax+1.

Question 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.)

Answer 63

-2147483647-1 < -2147483647.
(Note that TMax=2147483647.)
Type: Signed
Value: True, as -2147483647-1 = TMin, and -2147483647 = = TMin+1.

Question 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.)

Answer 64

-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.

Question 65

True or false? The conversion between a signed and unsigned integer is based on a numeric perspective rather than a bit-level one.

Answer 65

False, conversion is based on the bit-level perspective.

Question 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: \_\_\_\_\_\_\_\_\_

Answer 66

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.

Question 67

What is zero extension?

Answer 67

Zero extension is used to extend an unsigned integer to a larger data type.

This operation involves adding leading zeros to the bit representation.

Question 68

What is sign extension?

Answer 68

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.

Question 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

Answer 69

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

Question 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.

Answer 70

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.

Question 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.

Answer 71

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.

Question 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.

Answer 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++)
// 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;
}

Question 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.

Answer 73

/* 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);”

Question 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?

Answer 74

Original: C [1100]
Truncated: 4 [100]
Unsigned: 4
Two’s complement: -4

Question 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?

Answer 75

Original: C [1110]
Truncated: 4 [110]
Unsigned: 6
Two’s complement: -2

Question 76

Suppose x and y are two unsigned integers. Assuming their sum overflows, what is the result of their sum calculated?

Answer 76

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)

Question 77

Suppose x and y are two unsigned integers, and their sum overflows. How can this overflow be detected?

Answer 77

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.

Question 78

Suppose x and y are two two’s complement integers. Assuming their sum overflows, what is the result of their sum calculated?

Answer 78

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

Question 79

Suppose x and y are two two’s complement integers, and their sum overflows. How can this overflow be detected?

Answer 79

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.

Question 80

How can the negation of the two’s complement integers, x, be calculated at the bit level?

Answer 80

As follows:

-x = ~x+1

Question 81

True or false? Unsigned integer multiplication and two’s complement integer multiplication at the bit level is equivalent.

Answer 81

True.

Question 82

Suppose x and y are two’s complement integers, and their product overflows. How can this overflow be detected?

Answer 82

Let p=xy, then overflow occurs if x is not equal to zero and p/x is not equal to y. As code:
int p=xy;
return (x!=0) && (p/x!=y));

Question 83

How can the multiplication of an integer x by the k-th power of 2 be calculated using a bit operation?

Answer 83

With the code: x<

Question 84

Given an number integer x. How can the multiplication x*7 be calculated using bit shifts and addition (not subtraction!)?

Answer 84

First note that the bit pattern of 7 is [111]. Thus:

x*7 = (x«2) + (x«1) + x

Question 85

Given an number integer x. How can the multiplication x*7 be calculated using bit shifts and subtraction (not addition!)?

Answer 85

First note that the bit pattern of 7 is [111]. Thus:

x*7 = (x«3) - x

Question 86

True or false? Integer division always rounds toward negative infinity.

Answer 86

False. It round towards zero.

Question 87

How can the division of an unsigned integer, x, by the k-th power of 2 be calculated using bit shifts?

Answer 87

By applying a logical right-shift to x. Given by the code:
x»k

This automatically rounds the result towards zero.

Question 88

How can the division of a two’s complement integer, x, by the k-th power of 2 be calculated using bit shifts?

Answer 88

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.

Question 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)

Answer 89

False, x=TMin.

Question 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)

Answer 90

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.

Question 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

Answer 91

False, any integer x for which xx is large enough to cause positive overflow will ensure that the result of xx is a negative integer.

Question 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)

Answer 92

True. If x is nonnegative, then -x is nonpositive.

Question 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)

Answer 93

False. Let x be −2,147,483,648 (TMin32). Then both x and -x are negative.

Question 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

Answer 94

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.

Question 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) + uyux == -x

Answer 95

True. ~y equals -y-1. uyux equals xy. Thus, the left-hand side is equivalent to (x(-y))-x+xy (with all of the numbers converted to unsigned integers).

Question 96

What is the general form of an IEEE floating-point number?

Answer 96

V=(-1)^s * 2^E * M, where s is the sign, E is the exponent and M is the significand, or mantissa.

Question 97

How the bits in a “double” shared in the representation of the terms in V=(-1)^s * 2^E * M.

Answer 97

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.

Question 98

The value encoded by a given bit representation of an IEEE floating-point number can be divided into three cases. What are they?

Answer 98

1. Normalised numbers.
2. Denormalised numbers.
3. Special values (infinity and NaN).

Question 99

What are two purposes of using denormalised values?

Answer 99

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.

Question 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.

Answer 100

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.

Question 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?

Answer 101

The “implied leading 1” representation.

Question 102

What are the conditions necessary for the value encoded by an IEEE floating-point number to be a normalised value?

Answer 102

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.

Question 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.

Answer 103

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.

Question 104

What are the conditions necessary for the value encoded by an IEEE floating-point number to be a denormalised value?

Answer 104

Each of the k=11 bits after the sign bit (used to represent the exponent) must be equal to zero.

Question 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.

Answer 105

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.

Question 106

What are the conditions necessary for the value encoded by an IEEE floating-point number to be a “special” value?

Answer 106

Each of the k=11 bits after the sign bit (used to represent the exponent) must be equal to one.

Question 107

How does an IEEE floating-point number represent an infinity?

Answer 107

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.

Question 108

How does an IEEE floating-point number represent NaN?

Answer 108

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.

Question 109

Does an IEEE floating-point number have a symmetric range of values?

Answer 109

Yes.

Question 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.

Answer 110

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.

Question 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.

Answer 111

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.

Question 112

True or false? Floating-point addition and multiplication are commutative and associative.

Answer 112

False. Floating-point addition and multiplication are commutative but not associative.

Question 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

Answer 113

(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.

Question 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

Answer 114

(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.