Can't understand this way to calculate the square of a number

Question

I have found a function that calculates square of a number:

int p(int n) {
    int a[n]; //works on C99 and above
    return (&a)[n] - a;
}

It returns value of n². Question is, how does it do that? After a little testing, I found that between (&a)[k] and (&a)[k+1] is sizeof(a)/sizeof(int). Why is that?

Answer 1

Obviously a hack... but a way of squaring a number without using the * operator (this was a coding contest requirement).

(&a)[n] 

is equivalent to a pointer to int at location

(a + sizeof(a[n])*n)

and thus the entire expression is

  (&a)[n] -a 

= (a + sizeof(a[n])*n -a) /sizeof(int)

= sizeof(a[n])*n / sizeof(int)
= sizeof(int) * n * n / sizeof(int)
= n * n

Answer 2

To understand this hack, first you need to understand the pointer difference, i.e, what happens when two pointers pointing to elements of same array are subtracted?

When one pointer is subtracted from another, the result is the distance (measured in array elements) between the pointers. So, if p points to a[i] and q points to a[j], then p - q is equal to i - j.

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. [...].
In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

Now I am expecting that you are aware of array name conversion to pointer, a converts to pointer to first element of array a. &a is address of the entire memory block, i.e it is an address of array a. The figure below will help you to understand (_{read this answer for detailed explanation}):

This will help you to understand that why a and &a has the same address and how (&a)[i] is the address of i^th array (of same size as that of a).

So, the statement

return (&a)[n] - a; 

is equivalent to

return (&a)[n] - (&a)[0];  

and this difference will give the number of elements between the pointers (&a)[n] and (&a)[0], which are n arrays each of n int elements. Therefore, total array elements are n*n = n².

---

NOTE:

C11: 6.5.6 Additive operators (p9):

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined.

Since (&a)[n] neither points to elements of the same array object nor one past the last element of the array object, (&a)[n] - a will invoke undefined behavior.

Also note that, better to change the return type of function p to ptrdiff_t.

Answer 3

a is a (variable) array of n int.

&a is a pointer to a (variable) array of n int.

(&a)[1] is a pointer of int one int past the last array element. This pointer is n int elements after &a[0].

(&a)[2] is a pointer of int one int past the last array element of two arrays. This pointer is 2 * n int elements after &a[0].

(&a)[n] is a pointer of int one int past the last array element of n arrays. This pointer is n * n int elements after &a[0]. Just subtract &a[0] or a and you have n.

Of course this is technically undefined behavior even if it works on your machine as (&a)[n] does not point inside the array or one past the last array element (as required by the C rules of pointer arithmetic).

Answer 4

If you have two pointers that point to two elements of the same array then its difference will yield the number of elements between these pointers. For example this code snippet will output 2.

int a[10];

int *p1 = &a[1];
int *p2 = &a[3];

printf( "%d\n", p2 - p1 ); 

Now let consider expression

(&a)[n] - a;

In this expression a has type int * and points to its first element.

Expression &a has type int ( * )[n] and points to the first row of imaged two dimensional array. Its value matches the value of a though types are different.

( &a )[n]

is n-th element of this imaged two dimensional array and has type int[n] That is it is n-th row of the imaged array. In expression (&a)[n] - a it is converted to the address of its first element and has type `int *.

So between (&a)[n] and a there are n rows of n elements. So the difference will be equal to n * n.

Answer 5

Expression     | Value                | Explanation
a              | a                    | point to array of int elements
a[n]           | a + n*sizeof(int)    | refer to n-th element in array of int elements
-------------------------------------------------------------------------------------------------
&a             | a                    | point to array of (n int elements array)
(&a)[n]        | a + n*sizeof(int[n]) | refer to n-th element in array of (n int elements array)
-------------------------------------------------------------------------------------------------
sizeof(int[n]) | n * sizeof(int)      | int[n] is a type of n-int-element array

Thus,

1. type of (&a)[n] is int[n] pointer
2. type of a is int pointer

Now the expression (&a)[n]-a performs a pointer substraction:

  (&a)[n]-a
= ((a + n*sizeof(int[n])) - a) / sizeof(int)
= (n * sizeof(int[n])) / sizeof(int)
= (n * n * sizeof(int)) / sizeof(int)
= n * n