How is arithmetic with &array defined

Question

I get most of pointer arithmetic, until I saw the following:

int x[5];
sizeof(x)  // equals 20
sizeof(&x) // equals 4 -- sizeof(int))

So far I give this the semantic meaning of: pointer to N-element array of T -- in the case of &x

However when doing x+1 we increment with sizeof(int) and when we do &x+1 we increment with sizeof(x).

Is there some underlying logic to this i.e. some equivalences, because this feels very unintuitive.

/edit, thanks to @WhozCraig I came to the conclusion that I made an error:

sizeof(&x) // equals 4 -- sizeof(int)) 

Should be

sizeof(&x) // equals 8 -- sizeof(int))

Lesson learned: Don't post code you haven't run directly

Answer 1

Its called typed pointer math (or typed-pointer-arithmetic) and is intuitive when you get one thing engrained in your DNA: Pointer math adjusts addresses based on the type of a pointer that holds said-address.

In your example, what is the type of x? It is an array of int. but what is the type of the expression x ? Hmmm. According to the standard, the expression value of x is the address of the first element of the array, and the type is pointer-to-element-type, in this case, pointer-to-int.

The same standard dictates that for any data var (functions are a little odd) using the & operator results in an address with a type of pointer-to-type, the type being whatever the type of the variable is:

For example, given

int a;

the expression &a results in an address who's type is int *. Similarly,

struct foo { int x,y,z } s;

the expression &s results in an address who's type is struct foo *.

And now, the point of probable confusion, given:

int x[5];

the expression &x results in an address who's type is int (*)[5], i.e. a pointer to an array of five int. This is markedly different than simply x which is, per the standard, evals as an address who's type is a pointer to the underlying array element type

Why does it matter? Because all pointer arithmetic is based on that fundamental type of the expression address. Adjustments therein using typed pointer math are reliant on that fundamental concept.

int x[5];
x + 1

is effectively doing this:

int x[5];
int *p = x;
p + 1        // results is address of next int

Whereas:

&x + 1

is effectively doing this:

int x[5];
int (*p)[5] = &x;
p + 1         // results in address of next int[5] 
              // (which, not coincidentally, there isn't one)

---

Regarding the sizeof() differential, once again, those pesky types come home to roost, and in particular difference, it is important to note that sizeof is a compile-time operator; not run-time:

int x[5]
size_t n = sizeof(x);

In the above, sizeof(x) equates to sizeof(type-of x). Since x is int[5] and int is apparently 4 bytes on your system, the result is 20. Similarly,

int x[5];
size_t n = sizeof(*x);

results with sizeof(type-of *x) begin assigned to n. Because *x is of type int, this is synonymous with sizeof(int). The compile-time aspects, incidentally, make the following equally valid, though admittedly it looks a little dangerous at first glance:

int *p = NULL;
size_t n = sizeof(*p);

Just as before, sizeof(type-of *p) equates to sizeof(int)

But what about:

int x[5];
size_t n = sizeof(&x);

Here again, sizeof(&x) equates to sizeof(type-of &x). but we just covered what type &x is; its int (*)[5]. I.e. Its a data pointer type, and as such, its size will be the size of a pointer. On your rig, you apparently have 32bit pointers, since the reported size is 4.

An example of how &x is a pointer type, and that indeed all data pointer types result in a similar size, I close with the following example:

#include <stdio.h>

int main()
{
    int x[5];
    double y[5];
    struct foo { char data[1024]; } z[5];

    printf("%zu, %zu, %zu\n", sizeof(x[0]), sizeof(x), sizeof(&x));
    printf("%zu, %zu, %zu\n", sizeof(y[0]), sizeof(y), sizeof(&y));
    printf("%zu, %zu, %zu\n", sizeof(z[0]), sizeof(z), sizeof(&z));

    return 0;
}

Output (Mac OSX 64bit)

4, 20, 8
8, 40, 8
1024, 5120, 8

Note the last value size reports are identical.

Answer 2

You said "I get most of pointer arithmetic, until I saw the following:"

int x[5];
sizeof(x)  // equals 20
sizeof(&x) // equals 4 -- sizeof(int))

Investigating the first sizeof...

if ((sizeof(int) == 4) == true) {
   then the size of five tightly packed ints is 5 * 4
   so the result of (sizeof(int[5]) is 20.
}

However...

if (size(int)) == 4) is true
   then when the size of the memory holding the value of another memory address is 4,
   ie. when ((sizeof(&(int[5])) == 4) {
      it is a cooincidence that memory addresses conveniently fit 
      into the same amount of memory as an int.
   }
}

Don't be fooled, memory addresses have traditionally been the same size as int on some very popular platforms, but if you ever believe that they are the same size, you will prevent your code from running on many platforms.

To further drive the point home

it is true that (sizeof(char[4]) == 4),
but that does not mean that a `char[4]` is a memory address.

Now, in C, the offset operator for memory addresses "knows" the offset based on the type of pointer, char, int, or the implied address size. When you add to a pointer, the addition is translated by the compiler to an operation that looks more like this

addressValue += sizeof(addressType)*offsetCount

where

&x + 1

becomes

x += sizeof(x)*1;

Note that if you really want to have (some very unsafe programming) fun, you can cast your pointer type unsafely and specify offsets that really "don't work" the way they should.

int x[5];
int* xPtr = &x;
char* xAsCharPtr = (char*) xPtr;
printf("%d", xAsCharPtr + 2);

will print out a number comprised of about 1/2 the bits of numbers at x[0] and x[1].

Answer 3

It seems implicit conversion is at play, thanks to the excellent answer in some other pointer arithmetic question, I think it boils down to:

when x is an expression it can be read as &x[0] due to implicit conversion, adding 1 to this expression intuitively makes more sense that we want &x[1]. When doing sizeof(x) the implicit conversion does not occur giving the total size of object x. Arithmetic with &x+1 makes sense also when considering that &x is a pointer to a 5-element array.

The thing that does not become intuitive is sizeof(&x), one would expect it to also be of size x, yet it is the size of an element in the pointed-to array, x.

Answer 4

x is of type int[5], so &x is a pointer to an integer array of five elements, when adding 1 to &x you are incrementing to to next array of 5 elemnts.