Integers

Overview

Integers are typically encoded using either unsigned encoding or two's-complement. The following table highlights how the min and max of these encodings behave:

Value	$w = 8$	$w = 16$	$w = 32$
$U M i n_{w}$	`0x00`	`0x0000`	`0x00000000`
$U M a x_{w}$	`0xFF`	`0xFFFF`	`0xFFFFFFFF`
$T M i n_{w}$	`0x80`	`0x8000`	`0x80000000`
$T M a x_{w}$	`0x7F`	`0x7FFF`	`0x7FFFFFFF`

The width of an integer type refers to the number of bits used in the type's binary representation. It's precision refers to the number of bits used in the type's binary representation, excluding those used for signedness.

Unsigned Encoding

Always represents nonnegative numbers. Given an integral type $\vec{x}$ of $w$ bits, we convert binary to its unsigned encoding with:

B 2 U_{w} (\vec{x}) = 2^{w - 1} x_{w - 1} + \sum_{i = 0}^{w - 2} 2^{i} x_{i}

Note we unfold the summation on the RHS by one term to make it's relationship to $T 2 U_{w}$ clearer.

Two's-Complement

Represents negative numbers along with nonnegative ones. Given an integral type $\vec{x}$ of $w$ bits, we convert binary to its twos'-complement encoding with:

B 2 T_{w} (\vec{x}) = - 2^{w - 1} x_{w - 1} + \sum_{i = 0}^{w - 2} 2^{i} x_{i}

Casting

Most implementations of C cast an object of signed type to unsigned type and vice versa, most implementations simply re-interpret the object's binary representation. This casting may happen implicitly if comparing or operating on signed and unsigned objects in the same expression. $T 2 U$ and $U 2 T$ reflect this method of casting:

\begin{aligned} T 2 U_{w} (x) & = {\begin{cases} x + 2^{w} & x < 0 \\ x & x \geq 0 \end{cases} \\ U 2 T_{w} (x) & = {\begin{cases} x & x \leq T M a x_{w} \\ x - 2^{w} & x > T M a x_{w} \end{cases} \end{aligned}

Expansion

For unsigned encoding, use zero extension to convert numbers to larger types. For example, $1010_{2}$ can be expanded to 8-bit $00001010_{2}$ .

For two's-complement, use sign extension to convert numbers to larger types. This means the additional leftmost bits are set to match the sign bit of the original number. For example, $1010_{2}$ can be expanded to 8-bit $11111010_{2}$ .

Truncation

Let $x = ⟨ x_{w - 1}, \dots, x_{1}, x_{0} ⟩$ and $x^{'} = ⟨ x_{k - 1}, \dots, x_{1}, x_{0} ⟩$ .

In unsigned encoding, truncating $x$ to $k$ bits is equal to $x mod 2^{k}$ . This is because $x_{i} mod 2^{k} = 0$ for all $i \geq k$ meaning

B 2 U_{k} (x^{'}) = B 2 U_{w} (x) mod 2^{k} .

In two's-complement encoding, truncating $x$ to $k$ bits is equal to $U 2 T_{k} (T 2 U_{w} (x) mod 2^{k})$ . Like with unsigned truncation, $B 2 U_{k} (x^{'}) = B 2 U_{w} (x) mod 2^{k}$ . Therefore

U 2 T_{k} (B 2 U_{k} (x^{'})) = U 2 T_{k} (B 2 U_{w} (x) mod 2^{k}) .

Arithmetic

Addition

Addition of two unsigned or two two's-complement numbers operate in much the same way as grade-school arithmetic. Digits are added one-by-one and overflows "carried" to the next summation. Overflows are truncated; the final carry bit is discarded in the underlying bit adder.

Unsigned addition of $w$ -bit integral types, denoted $+_{w}^{u}$ , behaves like so:

x +_{w}^{u} y = {\begin{cases} x + y - 2^{w} & if x + y \geq 2^{w} \\ x + y & otherwise \end{cases}

This is more simply expressed as $x +_{w}^{u} y = (x + y) mod 2^{w}$ .

Two's-complement addition, denoted $+_{w}^{t}$ operates similarly:

x +_{w}^{u} y = {\begin{cases} x + y - 2^{w} & if x + y \geq 2^{w - 1} \\ x + y + 2^{w} & if x + y < - 2^{w - 1} \\ x + y & otherwise \end{cases}

Unlike with unsigned addition, there is no simpler modulus operation that can be applied.

Shifting

Left shift operations (<<) drop the k most significant bits and fills the right end of the result with k zeros. Right shift operations (>>) are classified in two ways:

Logical
- Drops the k least significant bits and fills the left end of the result with k zeros.
- This mode is always used when calling >> on unsigned data.
- Sometimes denoted as >>> to disambiguate from arithmetic right shifts.
Arithmetic
- Drops the k least significant bits and fills the left end of the result with k copies of the most significant bit.
- This mode is usually used when calling >> on signed data.

In C, it is undefined behavior to shift by more than the width $w$ of an integral type or by a negative value.

Multiplication

Unsigned multiplication, denoted with the $*_{w}^{u}$ operator, is defined as follows:

x *_{w}^{u} y = (x \cdot y) mod 2^{w}

Similarly, two's-complement multiplication is defined as follows: $$x *_w^t y = U2T_w((x \cdot y) \bmod 2^w)$$

Division

Integer division divides the result and discards any fractional result. This has the same effect as rounding toward zero.