Ints

The type int is the only numeric type in C0. We would like to think of it as the type of integers ..., -3, -2, -1, 0, 1, 2, 3, ... but this is not quite correct because its values only cover a fixed range, namely from -2³¹ to 2³¹-1, inclusively. To understand the reasons requires a brief detour to talk about the underlying machine model; to understand what this means for the usual arithmetic operations requires a brief detour to talk about modular arithmetic.

## Machine Model

C0 is a relatively low-level, imperative language that was designed to have a close relationship to the code executed by the processor of your computer. This processor's instructions directly operate on registers that have a fixed size. This native word size is the number of bits (0 or 1) that can be stored and manipulated by single instructions. Throughout history the word size of processors has increased, as design and manufacturing techniques have improved. Modern processors have a word size of 64 bits, although they are often used as if the word size was just 32 bits. In order for the basic operators to map directly to machine instructions, the size of the basic representation of integers in C0 was chosen to be 32 bits.

How many different values of type int are there? One bit can have 2 values (0 or 1), two bits have 2 * 2 = 4 values, three bits have 2 * 2 * 2 = 8 values, etc., since we can chose the bits independently. In general, a word of k bits can have 2^k different values. So the type int has 2³² = 4,294,967,296 (about 4 billion) different values. If you know something about the binary number system, you might expect these values to be 0, 1, 2, 3, ..., 4,294,967,295, where 0 is represented as 00000000000000000000000000000000 and 4,294,967,295 as 11111111111111111111111111111111. However, this would mean we would have no negative numbers at all (and it would seem pretty convenient to have, for example, -1 as a value). Furthermore, we have to consider what happens if operations such as addition overflow. To understand these two issues, we need a basic understanding of modular arithmetic and two's complement representation.

## Modular Arithmetic

The basic idea behind modular arithmetic is to fix a modulus m > 1 and then restrict numbers to the range 0, 1, 2, ..., m-1. We count as follows: 0, 1, 2, ..., m-1, 0, 1, 2, ..., m-1, 0, ..., so the the successor to m-1 is 0. Another way to think about it is that every arithmetic operation is performed modulo m, that is, we always take the remainder after dividing by m.

For example, if we perform arithmetic modulo 16, then 15+3 = 2 (mod 16) because 15+3 = 18, and 18 divided by 16 leaves a remainder of 2. It is remarkable that almost all the usual arithmetic laws you have learned in high school still hold when we do modular arithmetic. For example, multiplication distributed over addition (a + b) * c = a * c + b * c (mod m) for any modulus m. But we have to be careful with comparisons. For example, it is not necessarily the case that a+1 > a because we wrap around back to 0 (for example, 15+1 < 15 (mod 16)).

The elegant answer to the question how the processor performs arithmetic given a fixed word size w is arithmetic modulo 2^w. We just need to figure out how to get negative numbers into the picture...

## Two's Complement Representation