Is an Array Index content stored in one memory address?

Question

Assume in C we have the following array of one item:

int a[] = {2000};

2000 in binary would be:

11111010000

If each memory address can hold 1 byte (8 bits) of data, then howcome in some tutorials, it is mentioned that each array index is stored in one memory address? it's not possible since 2000 has 11 bits and needs at least 2 memory addresses to be stored.

My second question is, if it is stored in 2 (or more) memory addresses, how does the CPU know when to stop reading bits of the memory addresses? how does it know it has reached the end of the variable a above?

Answer 1

Consider the following program:

#include <stdio.h>

int main(int argc, char* argv[]) {
    int a[] = {2000, 3000};
    printf("%p %p\n", &a[0], &a[1]);
    return 0;
}

This prints the addresses of the elements of the array. For one run on my machine:

0x7ffc963400c0 0x7ffc963400c4

Notice they are 4 apart. For an int array, each array index skips sizeof(int) memory addresses. This is the same for all types of arrays, including arrays of structs. The array index identifies the element, not the byte.

Answer 2

If each memory address can hold 1 byte (8 bits) of data

That’s not exactly right—it’s not that memory is partitioned into an array of boxes, each of which is 1 byte in size; it’s that 1 byte is the smallest addressable unit of memory. You can address memory in larger increments.

So if you have a pointer char *p containing some address such as 0x12345670, that’s essentially just an offset into memory—it points to the start of a region that may comprise a single byte, or multiple bytes, such as an integer, array, or struct. (In fact it’s slightly more complicated, since what you see as a flat address space is actually virtual memory that’s mapped onto physical memory by the operating system kernel, but for the purposes of this explanation it doesn’t make a difference.)

A 32-bit integer with value 0xAABBCCDD at address p simply occupies 4 bytes. These bytes may be arranged by the CPU in big-endian order, where the most significant bits are stored at the lowest address:

0x1234566F …
0x12345670 0xAA
0x12345671 0xBB
0x12345672 0xCC
0x12345673 0xDD
0x12345674 …

Or little-endian, where the least significant bits are stored at the lowest address:

0x1234566F …
0x12345670 0xDD
0x12345671 0xCC
0x12345672 0xBB
0x12345673 0xAA
0x12345674 …

A programming language like C abstracts over this somewhat to provide a convenient way to address objects of different sizes. Suppose there is some array of 32-bit integers a, and p is the address of the first element: p = &a[0]. In assembly, if you want to iterate over this array, you need to increment p by 4 each time to move it to the next integer:

&a[0] == p
&a[1] == p + 4
&a[2] == p + 8
&a[3] == p + 12
&a[4] == p + 16
…

In C, an expression like p + 1 doesn’t just add a number of bytes to the value of p, it adds multiples of the object size, sizeof(*p)—so if p were typed as uint32_t *p, then a[1] would be at p + 1, a[2] at p + 2, and so on. Under the hood, p + n becomes something like (char *)p + n * sizeof(*p).

how does the CPU know when to stop reading bits of the memory addresses?

A primitive type like an integer is always a fixed size. When you write *pi += 42 to add 42 to the contents of the 32-bit integer referred to by pi, that’s translated specifically to a 32-bit indirect-add instruction. A compound type like an array is just a series of values at addresses that are multiples of the object size—your program is responsible for only accessing within the bounds of the array. Higher-level languages insert automatic checks at runtime or compile-time to ensure memory safety by preventing invalid array accesses, among other things.

A dynamically allocated value like the result of malloc is just a region of memory that the allocator has given you control over, which in turn it obtains from the operating system. You can cast it to whatever type you want, such as an array of custom structures, as long as you only access within the region that you’ve been granted by the allocator.

Answer 3

If each memory address can hold 1 byte (8 bits) of data, then how come in some tutorials, it is mentioned that each array index is stored in one memory address? it's not possible since 2000 has 11 bits and needs at least 2 memory addresses to be stored.

Yes, each memory address can hold a byte.  However, often a block of memory is used to store things — this means using memory locations at consecutive memory addresses to store something larger than a byte.  An int is often 4 bytes long, for example; however, we can also store structs and objects that are even larger, not to mention arrays.

My second question is, if it is stored in 2 (or more) memory addresses, how does the CPU know when to stop reading bits of the memory addresses? how does it know it has reached the end of the variable a above?

CPUs support multiple data types in that: they have instruction encodings for byte load, word load, and long word load, and a floating point load.  When it comes to larger items like a struct or an object, the compiler will generate multiple instructions (perhaps inline, perhaps in a loop, or maybe by calling a helper function in the library, i.e. something like memmove to copy a larger structure).

The CPU simply does what it is instructed to do by the code generated by the compiler.  The compiler chooses storage location & layout for variables.  After that, the compiler generates instructions to access those storage locations.

Note that all the CPU does is execute the (compiler or assembly) programmed instructions, which tell it how to operate on what data in tiny steps — the CPU doesn't know about the location & layout of variables per se, it just executes little instructions (really fast).

So, it is the compiler's job to generate coherent instruction streams for the CPU that are true to the meaning of the source code.  The definition of the language (e.g. the C standard) tells the compiler (or compiler writer) the meaning of language constructs found in the source code and this guides the translation to machine code.

Answer 4

@Josepha said "ok but isn't ONE memory address only one byte?".

Not in C. The C language defines an abstract machine that is an overlay on the hardware architecture. The compiler arranges for things to appear as though you are running on the abstract machine, but emitting the necessary code for that specific architecture. There is no virtual or physical address space in C, only the pointers to objects and pointer to void, specified in the standard. When you work with a pointer in C, you have a token that represents a storage location, not a memory address. That pointer value, might actually have a bit pattern that matches that of an address bus bit pattern, but that's not relevant here.

When you have a pointer to an int, it points to an object that has sizeof(int), not sizeof physical memory cell.