Offset between two array element addresses in C

Question

I have a question asking me to find the offset in bytes between two array element addresses:

double myArray[5][7];

If C stored data in column-major order the offset (in bytes) of &myArray[3][2] from &myArray[0][0] would be:

In column major order, I think elements would be laid out as such:

[0][0] -- [1][0] -- [2][0] -- [3][0] -- ..... -- [3][2]

So in my mind to get the offset in bytes is to count the number of jumps between [0][0] and [3][2] and times that by 8 since it's an array of doubles. However, what's confusing me is that it's asking for the offset using the & operator. Would this somehow change the answer since it's asking between two addresses or is the process still the same? I think it'd be the same but I'm not 100% certain.

If my thinking is correct would this then be 8*15 bytes?

Answer 1

The memory lay out for the 2d array would be a contiguous chunk of memory.(Based on your question)

int x[2][3] = {{0,1,2},{3,4,5}};

That will be layed out in (Your question)

--+--+--+--+--+--+
 0| 3| 1| 4|2 |5 |
--+--+--+--+--+--+

But in C this is stored like

--+--+--+--+--+--+
 0| 1| 2| 3|4 |5 |
--+--+--+--+--+--+

Now you are absolutely right, that you can consider jumps between [0][0] and [3][2] but there is a better way to do that without thinking about all this, you can be sure that their offset will be their address differences.

You can simply get their addresses and subtract them.

ptrdiff_t ans = &a[3][2]-&a[0][0];(this is basically the gaps between the two elements)

That yields the answer. printf("answer = %td",ans*sizeof(a[0][0]); (One gap = sizeof(a[0][0])) [In your case double]

Or even better way would be to

ptrdiff_t ans = (char*)&a[3][2] - (char*)&a[0][0];//number of bytes between them.

---

I will explain a bit why char* is important here:

(char*)&a[0][0] and &a[0][0] both contain the same thing value-wise.(this is not general enough)

But it matters in pointer arithmetic. (Interpretation is different).

When not using the cast, the interpretation is of the data type of array elements. That means now it consider the difference in doubles. When you cast it, it spits the result in or difference in char-s.

And why this works? Because all data memory is byte addressable and char is of single bytes.

---

There is something more to this than expected , first let's see what is an array in C? ^†

C does not really have multi-dimensional arrays. In C it is realized as an array of arrays. And yes those multidimensional array elements are stored in row-major order.

To clarify a bit more we can look into an example of standard §6.5.2.1

Consider the array object defined by the declaration

      int x[3][5];

Here x is a 3 x 5 array of ints; more precisely, x is an array of three element objects, each of which is an array of five ints. In the expression x[i], which is equivalent to (*((x)+(i))), x is first converted to a pointer to the initial array of five ints. Then i is adjusted according to the type of x, which conceptually entails multiplying i by the size of the object to which the pointer points, namely an array of five int objects. The results are added and indirection is applied to yield an array of five ints. When used in the expression x[i][j], that array is in turn converted to a pointer to the first of the ints, so x[i][j] yields an int.

So we can say double myArray[5][7]; here myArray[3][2] and myArray[0][0] are not part of the same array.

Now that we are done here - let's get into something else:

From standard §6.5.6.9

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.

But here myArray[3] and myArray[0] are denoting two different arrays. And that means myArrayp[3][2] and myArray[0][0] both belong to different arrays. And they are not one past the last element. So the behavior of the subtraction &myArray[3][2] - &myArray[0][0] will not be defined by the standard.

^†_{Eric (Eric Postpischil) pointed out this idea.}

Answer 2

The Simple Answer

C does not have multidimensional arrays, so we have to interpret double myArray[5][7] as one-dimensional array of one-dimensional arrays. In double myArray[5][7], myArray is an array of 5 elements. Each of those elements is an array of 7 double.

Thus, we can see that myArray[0][0] and myArray[0][1] are both members of myArray[0], and they are adjacent members. Thus, the elements proceed [0][0], [0][1], [0][2], and so on.

When we consider myArray[1], we see it comes after myArray[0]. Since myArray[0] is an array of 7 double, myArray[1] starts 7 double after myArray[0].

Now we can see that myArray[3][2] is 3 arrays (of 7 double) and 2 elements (of double) after myArray[0][0]. If a double is 8 bytes, then this distance is 3•7•8 + 2•8 = 184 bytes.

The Correct Answer

To my surprise, I cannot find text in the C standard that specifies that the size of an array of n elements equals n times the size of one element. Intuitively, it is “obvious”—until we consider that an implementation in an architecture without a flat address space might have some issues that require it to access arrays in complicated ways. Therefore, we do not know what the size of an array of 7 double is, so we cannot calculate how far myArray[3][2] is from myArray[0][0] in general.

I do not know of any C implementations in which the size of an array of n elements is not n times the size of one element, so the calculation will work in all normal C implementations, but I do not see that it is necessarily so according to the C standard.

Calculating the Distance in a Program

It has been suggested the address can be calculated using (char *) &myArray[3][2] - (char *) &myArray[0][0]. Although this is not strictly conforming C, it will work in common C implementations. It works by converting the addresses to pointers to char. Subtracting these two pointers then gives the distance between them in units of char (which are bytes).

Using uintptr_t is another option, but I will omit discussion of it and its caveats as this answer is already too long.

A Wrong Way to Calculate Distance

One might think that &myArray[3][2] is a pointer to double and &myArray[0][0] is a pointer to double, so &myArray[3][2] - &myArray[0][0] is the distance between them, measured in units of double. However, the standard requires that pointers being subtracted must point to elements of the same array object or to one past the last element. (Also, for this purpose, an object can act as an array of one element.) However, myArray[3][2] and myArray[0][0] are not in the same array. myArray[3][2] is in myArray[3], and myArray[0][0] is in myArray[0]. Further, neither of them is an element of myArray, because its elements are arrays, but myArray[3][2] and myArray[0][0] are double, not arrays.

Given this, one might ask how (char *) &myArray[3][2] - (char *) &myArray[0][0] can be expected to work. Isn’t it also subtracting pointers to elements in different arrays? However, character types are special. The C standard says character pointers can be used to access the bytes that represent objects. (Technically, I do not see that the standard says these pointers can be subtracted—it only says that a pointer to an object can be converted to a pointer to a character type and then incremented successively to point to the remaining bytes of an object. However, I think the intent here is for character pointers to the bytes of an object to act as if the bytes of the object were an array.)

Answer 3

In a row-major traversal, the declaration is array[height][width], and the usage is array[row][column]. In row-major, stepping to the next number gives you the next column, unless you exceed the width and "wrap" to the next row. Each row adds width to your index, and each column adds 1, making rows the "major" index.

In order to get the column-major equivalent, you assume the next value is the next row, and when the row exceeds the height, it "wraps" to the next column. This is described by index = column * height + row.

So, for an array array[5][7] of height 5, the index [3][2] yields 2*5 + 3 = 13.

Let's verify with some code. You can get column-major behavior simply by switching the order of the indices.

#include <stdio.h>                                                                                                             

int main() {                                                                                                                   
    double array[7][5];                                                                                                    
    void *root = &array[0][0];                                                                                             
    void *addr = &array[2][3];                                                                                             
    size_t off = addr - root;                                                                                              
    printf("memory offset: %d number offset: %d\n", off, off/sizeof(double));                                                                        
    return 0;                                                                                                              
}

Running this program yields an address offset of 104, or 13 doubles.

EDIT: sorry for wrong answer