2章.

2.1 information storage

A machine-level program views memory as a very large array

of bytes,referred to as virtual memory.Every byte of

memory is identified by a unique number,known as its addr

,and the set of all possible addresses is known as the

virtual address space.

2.1.1 Hexadecimal Notation

converting a decimal number x to hexadecimal,we can re-

peatly divide x by 16,and using the remainder:

1227 = 76 * 16 + 11 //11 is b

76 = 4 * 16 + 12 //12 is c

4 = 0 * 16 + 4 // 4

so the hexadecimal number of 1227 is ox4cb //REVERSE

2.1.2 Date Sizes

Every computer has a word size,indicating the nominal

size of pointer data.Since a virtual address is encoded

by such a word,the most important sytem parameter deter-

mined by the word size is the maximum size of the vir-

tual address space.That is,for a machine with a w-bit

word size,the virtual addresses can range from 0 to 2^w-1

,giving the program access to at most 2^w bytes.

One aspect of portability is to make the program insensi-

tive to the exact sizes of the different data types.

2.1.3 Addressing and Byte Ordering

What the address of the object will be,and how we will

order the bytes in memory.In virtually all machines,a

multi-byte objects is stored as a contiguous sequence of

bytes,with the address of the object given by the

smallest address of the bytes used.

The least significant byte comes first to be stored in

memory is refferred to as "little endian".

a ^ 1 //make complement

a ^ 0 // keep same value

a ^ ~0xff //keep last two same,others make complement

2.2 Integer Representations

Bits can be used to encode integers:

one that can only represent nonnegative numbers,and

one that can represent negative,zero,and positive

numbers.

2.2.3

in the file "stdint.h":

intN_t forms for data types

INTN_MIN,INTN_MAX,and UINTN_MAX //macros

"limits.h" defines a set of constants

Conversion from two's complement to unsigned,for x such

that TMin <= x <= Tmax :

T2U(x) = x + 2 ^ w x < 0

x x >= 0

Conversion from unsigned number to signed:

U2T(u) = u, u <= Tmax

u - 2 ^ W u > Tmax

"always convert integer to unsigned when they together"

2.2.6 Expanding the bit representation of a number

principle:

Expansion of an unsigned number by zero extension

Expansion of a two's-complement number by sign ex-

tension.

"converting from short to unsigned int,first change"

"the size(int) and then the type(unsigned)"

2.2.7 Truncating Numbers

When truncating,just truncate directly. Truncating a

number can alter its value--a form of overflow.

2.3 Integer Arithmetic (page 84 - 104)

2.3.1 Unsigned Addition

x + y, x + y < 2 ^ w //normal

x + y =

x + y - 2 ^ w, 2^w <= x + y < 2 ^ w + 1//ovfl

Detecting overflow of unsigned addition

For x and y in the range 0 <= x,y <= umax, if s = x+y

.Then the computation of s overflowed if and only if

s < x (or equvalently,s < y).

2.3.2 Two's-Complement Addition

For integer values x and y in the range:

-2^(w-1) <= x,y<= 2^(W-1) - 1:

x + y - 2^w, 2^(w-1) <= x+y //positive overflo

x + y = x + y, -2^(w-1) <= x+y < 2^(w-1) //normal

x + y + 2^w, x+y < -2^(w-1) //negative overflo

Detecting overflow in two's-complement addition

for x and y in the range tmin <=x,y <= tmaxx,

positive overflow:

if x > 0 and y > 0 but sum <= 0.

negative overflow:

if x < 0 and y < 0 but sum >= 0.

One technique for performing two's-complement negation

at the bit level is to complement the bits and then

increment the result.In c, we can state that for any

integer value x, computing the "-x and ~x+1" will same

results.

A second way to performing two's-complement negation

of a number x is based on splitting the bit verctor

into two parts.keep the rightmost 1,and the rest of it

make a complement.

e.g: 1010 -> 01 10(KEEP THE LOWEST 1 BIT)

2.3.4 Unsigned Multiplication

For x and y such that 0 <= x,y <= UMAX:

x * y = (x*y)mod 2^w

2.3.5 Two's-Complement Multiplication

x * y = U2T((x*y)mod 2^w)

PRINCIPLE: Bit-level equivalence of unsigned and two's-

complement multiplication.

Determine whether arguments can be multiplied without

overflow:

int tmult_ok(int x,int y)

{

int p = x * y;

/* Either x is zero, or dividing p by x gives y */

return !x || p/x == y;

}

2.3.6 Multiplying by constants

multiply instruction on many machines was fairly slow,

so, one important optimization used by compliers is to

attempt to replace multiplications by constant factors

with combinations of shift and addition operations.

2.3.7 Dividing by powers of 2

Using shift operations.The two different right shifts:

logical and arithmetic, serve this purpose for unsigned

and two's-complement numbers,respectively.

"Integer division always rounds toward zero."

+ unsigned integer always round douw

+ signed integer round down but for negative,can use

"biasing" technica causing round up.

(x + (1 <<k) - 1) >> k.

The biasing technique exploits the property that:

x/y = (x+y-1)/y

For a two's-complement machine using arithmetic right

shifts,the C expression:

(x<0 ? x+(1<<k)-1 : x) >> k

// "(1<<k)-1 meaning k bits of 1."

will compute the value x/(2^k)

int div16(int x) { //(page 107 problem)

// Comute bias to be either 0(x>=0) or 15(x<0)

int bias = (x >> 31) & 0xF;

return (x + bias) >> 4;

}

2.3.8 Final Thoughts on Integer Arithmetic

2.4 Floating Point

A floating-point representation encodes rational numbers

of the form V = x * 2^y. It is useful for performing

computations involving very large numbers(|V|>>0),numbers

very close to 0(|V|<<1),and more generally as an approxi-

mation to real arithmetic.

2.4.4 Rouding

For a value x we generally want a systematic

method of finding the "closest" matching value X

that can be repersented in the desired floating-

point format. "This is the task of the rounding"

operation.

The IEEE floating-point format defines four

different rounding modes.The default method finds

a closest match,while the other three can be used

for computing upper and lower bounds.

1. round-to-even \\default

2. round-toward-zero

3. round-down

4. round-up

Round-to-even rounding can be applied to binary

fractional numbers.We consider least significant

bit value 0 to be even.

10.11100 --> 11.00 //the least significant

10.10100 --> 10.10 // bit equal to zero

note: xxx.yyy100....... 100 represent half way

2.4.5 Floating-point operations

(3.14 + 1e10) - 1e10 = 0.0 //lost due to rounding

3.14 + (1e10 - 1e10) = 3.14

floating-point addition satisfies the following

monotonicity property: if a >= b, then x + a >= x + b

floating-point multilication does not distribute over

addition.

floating-point multiplication satisfies the following

monotonicity properties for any values of a,b,an c

other than NaN:

a >= b and c >= 0 ==> a * c >= b * c

a >= b and c <= 0 ==> a * c <= b * c

from int or float to double,the exact numeric value

can be perserved because double has both greater range

from float or double to int,the value will be rounded

toward zero.

----------------------------------------------------------