Arrays and pointer arithmetic

Five ints sit side by side in memory. How does the machine find the fourth? Watch the address in p as it walks them.

1#include <stdio.h>2 3int main(void)4{5    int a[5] = { 4, 8, 15, 16, 23 };6    int sum = 0;7    for (int *p = a; p < a + 5; p++)8        sum = sum + *p;9    printf("sum = %d\n", sum);10    return 0;11}

One box after another

The five boxes of a sit one after another in memory, with no gaps: a[0] at 0x7fd0, a[1] 4 bytes later at 0x7fd4, and so on. That is the whole trick. To find a[3], the machine starts at 0x7fd0 and adds 3 × 4 = 12 bytes, which gives 0x7fdc. It never looks at a[0], a[1] or a[2] on the way.

Watch the tag above the strip. It is the pointer p, and the number it carries is the address in p. Each time the loop runs p++, the tag moves exactly one box, and the number goes up by 4, not by 1. Adding 1 to a pointer to int moves it to the next int.

Now press double. The boxes are 8 bytes wide, so the tag still moves one box per hop, and the address now goes up by 8. The step is always the size of one element.

At the end the tag lands on a dashed box past the last one, at 0x7fe4. That is a + 5. The loop compares p with it to know when to stop, and never reads the box there.

The code and its cost

Declaring and indexing

int a[5] = { 4, 8, 15, 16, 23 };

declares a as five int boxes in a row, 20 bytes, and fills them in order. The boxes are numbered from 0: a[0] is 4 and a[4] is 23. There is no a[5]; the five indices are 0 to 4.

a[i] reads or writes box i, like any variable: a[2] = 7; writes 7 into the third box.

a + i and *(a + i)

Used in an expression, the name a stands for the address of a[0], 0x7fd0 here. Adding a number to an address works in elements, not bytes: a + i is the address i boxes further on, i * sizeof a[0] bytes past a. For int, a + 2 is 0x7fd0 + 8 = 0x7fd8.

And a[i] means exactly *(a + i): go i boxes along from a, then read the box there. The square brackets are a shorter way to write the same thing. That is why indices start at 0: a[0] is *(a + 0), the box at a itself.

The walk

The program in the picture adds up the array by walking a pointer along it:

for (int *p = a; p < a + 5; p++)
    sum = sum + *p;

p starts at a, the address of a[0]. Each pass adds *p, the box p points to, then p++ moves p to the next box. After a[4], p becomes a + 5 and the test p < a + 5 fails. Line 8 runs five times, once for each box.

One past the end

C lets a pointer hold the address just past the last box, a + 5, so that a loop can compare against it. It does not let you follow it: there is no a[5], and *(a + 5) is undefined behaviour. On this machine, with this build, it reads whatever happens to lie next in memory. The picture draws that box dashed for this reason.

An array is not a pointer

a behaves like an address in an expression, but a itself is the 20 bytes of boxes, not a pointer box. Two things show it. sizeof a is 20, the whole array, where a pointer is 8. And a = a + 1; does not compile: an array cannot be moved. A pointer p can.

Passing an array to a function

Here is the sum written as a function, sum(const int *a, size_t n), and a main that calls it on the same five numbers. Watch what the call hands over.

1#include <stddef.h>2#include <stdio.h>3 4int sum(const int *a, size_t n)5{6    int total = 0;7    for (size_t i = 0; i < n; i++)8        total = total + a[i];9    return total;10}11 12int main(void)13{14    int a[5] = { 4, 8, 15, 16, 23 };15    printf("sum = %d\n", sum(a, 5));16    printf("sizeof a in main = %zu\n", sizeof a);17    return 0;18}

The program prints sum = 66, then sizeof a in main = 20. In the call sum(a, 5), a stands for the address of a[0], so what the function gets is one 8-byte pointer holding 0x7fd0, not the 20 bytes of boxes. Its own a is that pointer, and a[i] inside sum reads main’s boxes through it: watch total grow while main’s five boxes stay exactly as they were. Writing the parameter as int a[] changes nothing: it is still a pointer.

So inside sum, sizeof a is 8, the size of a pointer, and the function has no way to find out how many boxes there are. That is why the length travels beside the array, as n. The const from Passing pointers to functions (2.2) says sum only reads them.

No bounds checks

C does not check an index. With int a[5], a[5] compiles, but it is undefined behaviour. On this machine, with this build, it reads the 4 bytes after a[4], whatever they hold, and a[5] = 0; overwrites them. Memory errors (2.5) shows what that does and how to catch it.

What it costs

Finding a[i] is one multiplication and one addition, i × 4 added to the address of a, whatever i is: a[4] costs no more than a[0], and in an array of 5,000 boxes neither would a[4999]. Walking the whole array is one step per box, so n boxes take n steps.

Worked example

Take int a[5] = { 4, 8, 15, 16, 23 }; at 0x7fd0, as in the picture.

1. &a[3] is 0x7fd0 + 3 × 4 = 0x7fd0 + 12 = 0x7fdc.
2. *(a + 2) is the box 2 along from a[0]: 15.
3. After int *q = a + 1;, q points at a[1]. Then q[2] is *(q + 2), two boxes past a[1]: that is a[3], 16.
4. For the double array at 0x7fc0, each box is 8 bytes, so &a[3] is 0x7fc0 + 3 × 8 = 0x7fc0 + 24 = 0x7fd8.
5. An image of 640 × 480 pixels, one byte each, stored row after row in one array: the pixel in row 2, column 10 is element 2 × 640 + 10 = 1290.

Try it yourself. If p holds 0x7fd8 and points into the int array, what does p + 2 hold? Two ints on, 8 bytes: 0x7fe0, the address of a[4]. And what is &a[5]? 0x7fe4, an address you may compute and compare, never follow.

Where it’s used

Audio and sensor buffers. A sound or a sensor’s readings are stored as a long array of samples. Convolution, the heart of digital filtering, is a loop that walks such arrays with exactly these pointer steps.

Images. A picture is an array of pixels, row after row, and finding pixel (row, column) is the arithmetic of the worked example.

Tables. Chapter 5 builds searching, inserting and growing on arrays like this one.

Strings. A string in C is an array of char, one byte per box, which Chapter 6 takes apart.

Reference card

Platform: C11, gcc 13 on x86-64 Linux: int 4 bytes, double 8, pointers 8. The addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.