1 Representing and Manipulating Information

integer arithmetic: associative and commutative

floating-point arithmetic: not associative (but also commutative) (big number eats small number)

• Big endian: lower address contains more significant byte

• Intel, Android, iOS operate in little-endian mode

• bi-endian: can be configured to operate as either little- or big-endian (e.g. ARM microprocessors)

1. Integer

1.1 Basis

unsigned integer

signed integer / two's-complement:

(\(x_{w-1}\) represents the sign)

1.2 Conversion

Read two's-complement number's normal value:

• From right to left, starting with the bit after the 1st "1", inverse the bits → abs value
• If the sign bit is 1, the result is the value represented by the other bits minus \(2^w\)

Write two's-complement form of given value:

• Decide the sign bit, and use \(x + 2^w\) for the remaining bits

1.3 Comparison

If one of the number is unsigned, then compare the numbers by the unsigned rule. The same rule applies to other operations.

1.4 Expansion

Unsigned expansion is simple.

Signed expansion:

(can be proved by definition)

1.5 Truncation

Truncation is mod:

1.6 Arithmetic

1.6.1 Addition

Add the two's-complement form of the numbers directly, and illustrate the result as a two's-complement number.

1.6.2 Negation

At bit-level,

int8_t x = 12;  // 0000 1100
x = -x;                 // 1111 0100

At bit-level, -x == ~x + 1:

uint8_t x = 12; // 0000 1100
x = -x;                 // 1111 0100

uint8_t x = -12;    // 1111 0100
x = -x;                     // 0000 1100

1.6.3 Multiplication

Given that integer multiplication is more costly than shifting and adding, many C compilers try to remove many cases where an integer is being multiplied by a constant with combinations of shifting, adding, and subtracting.

For example, suppose a program contains the expression x*14. Recognizing that 14 = 23 + 22 + 21, the compiler can rewrite the multiplication as (x<<3) + (x<<2) + (x<<1) .

1.6.4 Division

Shifting right of negative two's-complement

1001 0000 >> 1 =
1100 1000

Keep the sign bit, and padding 1 to the left of the remaining bits.

Rounding to zero and rounding up/down

For Python,

>>> -13/3
-4.333333333333333
>>> -13//3
-5

(It's rounding down.)

For C,

(lldb) print -13/3.0
(double) $1 = -4.333333333333333
(lldb) print -13/3
(int) $2 = -4
(lldb)

(It's rounding to zero.)

So two’s-complement division by a power of 2 in C means the result should be rounded to zero, leading to the difference with simply shifting right.

2. Floating Point

2.1 IEEE Floating-Point Representation

• e is the unsigned number
• CAUTION: \(f = 0.f_{n-1} \dots f_0 = {f_{n-1} \dots f_0 \over 2^n}\)​

(NaN: not a number; e.g. \(\sqrt{-1}\), \(\infty - \infty\)​)

2.1.1 Floating Point Representation → Value

0 1110 101
s  e    f

Bias = 2^(4-1) - 1 = 7
E = e - 7 = 14 - 7 = 7
e != 0 => M = f + 1 = 5/2^3 + 1 = 13/8
Value = (-1)^0 * M * 2^E = 13/8 * 2^7 = 13*16 = 208

2.1.2 Value → Floating Point Representation

129
10000001

1.0000001 * 2^7
0 (e,E=e-Bias) (f,M=f+1) = M * 2^E
Bias = 2^(4-1) - 1 = 7
e = E+Bias = 7+7 = 14 -> 1110(bin)
f = M-1 = 0.0000001

0 1110 000

2.2 Rounding

Round-to-even is also called round-to-nearest .

Round to quater:
10.11100 -> 11.00
10.10100 -> 10.10

2.3 Operations

No associative property!

Satisfies:

1. closure of addition or multiplication:
   • although 0 * inf yields NaN
2. commutative: x*y = y*x, x+y = y+x
3. monotonicity:
   • if a≥b ,then x+a ≥ x+b for any values of a, b, and x other than NaN
   • 

---

Last update: September 7, 2021

Authors: Co1lin