# Notes for Introduction to Computer Systems: Integer Representation

Check out the course offered by CMU at

## Encoding byte values

• 1 byte = 8 bits
• Range from:
• Binary 00000000 to 11111111
• Decimal 0 to 255
• Hexidecimal 00 to FF

## Boolean algebra

### Relationship with set operation

• And (&) => intersection
A&B = 1 when A = 1 and B = 1
• Or (|) => union
A|B = 1 when either A = 1 or B = 1
• Not (~) => symmetric difference
~A = 1 when A = 0
• Exclusive-or (^) => complement
A^B = 1 when either A = 1 or B = 1, but not both

### Shift operations

• Left shift (x << y): throw away extra bit; fill with 0 on right
• Right shift (x >> y)
Logical shift: fill with 0 on left
Arithmetic shift: replicate MSB (most significant figure)
• Undefined: shift amount < 0 or >= word size

## Integer representation

• Unsigned:
$$B2U(X)=\sum_{i=0}^{w-1}x_i \cdot 2^i$$
e.g. $1011=1 \times 2^0 + 1 \times 2^1 + 0 \times 2^3 + 1 \times 2^4$
• Two’s complement:
$$B2T(X)=-x_{w-1} \cdot 2^{w-1} + \sum_{i=0}^{w-2} x_i \cdot 2^i$$
e.g. $1011 = −1 \times 2^3 + (1 \times 2^0 + 1 \times 2^1 + 0 \times 2^2 )$

### Numeric range of integer representations

Unsigned:
$$UMin=0=000 \ldots 0$$
$$UMax=2^{w−1}= 111 \ldots 1$$

Two’s complement
$$TMin=−2^{w−1}$$
$$TMax=2^{w−1}−1$$
(p.s. -110 = 111…12 in 2’s complement)

$$|TMin|=TMax+1$$
$$UMax=2\times TMax+1$$

### Mapping between signed and unsigned

• Keep bit representation and reinterpret
• Large negative becomes large positive
• $T2U(x)=x_(w−1) \cdot 2^w + x$
• Justification:
$$B2U(X)−B2T(X)=x_{w−1}\cdot[2^{w−1}−(−2^{w−1} )]=x_{w−1}\cdot(2\cdot2^{w−1} )=x_{w−1}\cdot2^w$$
$$B2U(X)=x_{w−1}\cdot2^w+B2T(X)$$
If we let $B2T(X)=x$, then, $B2U(T2B(x))=T2U = x_{w−1} \cdot 2^w + x$
• In expression containing signed and unsigned, signed is cast to unsigned

### Expanding

To convert w-bit signed integer to w + k bit integer with same value, make k copies of sign bit

• Justification
$$X=−2^{w−1} x_{w−1}$$
$$X’=−2^{w} x_{w−1}+2^{w−1} x_{w−1}=(−2^w+2^{w−1} ) x_{w−1}$$

### Why use unsinged

Don’t use just because number is nonnegative; do use when need extra bit’s worth of range

### Truncation (drop the high order w-k bits)

• Unsigned (w-bit to k-bit): $\mod 2^k$
• Two’s complement (w-bit to k-bit): Cast to unsigned then $\mod 2^k$