Home > Software design >  Does A[-1] actually returns the previous position in memory from A[0]?
Does A[-1] actually returns the previous position in memory from A[0]?

Time:09-18

Consider the following code:

int A[5] = {0,1,2,3,4};
int i=1;
int test = A[i];

The MIPS assembly that this code yields will shift i 2 bits left to multiply by 4, since we fetching an int (4 byte). I understand this completely.

Now if we set

int i = -1; //or any negative number

the assembly produced will actually be the same. But here, we are shifting a negative number by 2 bits, which could actually return a positive number. So, my question is, A[negative_number] will not offset the address by this negative number, but it will produce a somewhat random result, right?

CodePudding user response:

Left-shifting -1 2 bits yields -4, which is the correct byte offset to add to get the -1st position.

Left-shifting will only yield a positive number if i is extremely large such that the result overflows. But that could only happen if you were trying to access beyond the -229th index (assuming 32-bit ints), which is of course too large (small?) of an index to ask for in the first place.

By the way, accessing a negative index is only valid if you're starting with a pointer that's midway through an object and the negative index is still accessing valid memory. A[-1] would invoke undefined behavior. A better example would be:

int *p = &A[3];
int i = -1;
int test = p[i];

Here p[-1] resolves to (&A[3])[-1] which is equivalent to A[2]. That's a valid index, so p[-1] is legal.

Also, while in assembly code it's fine, it should be noted that left shifting negative numbers in C is undefined. Don't try to write -1 << 2 in your C code. The compiler can do it on our behalf but we're not allowed to write it ourselves.

What if you shift 100001 one time to the left? You will get 000010, which is positive in my books.

That would only be the case if ints were 6-bits wide. Per the C standard they must at least 16-bits wide, and in modern computers are usually 32-bits, and sometimes 64.

Let's say we were on a 16-bit system. 100001 would actually be one of these two numbers:

  • 0000000000100001. This is 33, a positive number.
  • 1111111111100001. This is -31, a negative number. Shifting it left would retain all but one of the leading 1 bits and remain negative.

CodePudding user response:

A[-1] does designate the element in memory before A[0] if such an element exists in the computing model the C standard uses. It does not if A is an array but may if A is a pointer:

int X[] = { 10, 11, 12, 13 };
int *A = &X[2];
printf("%d\n", A[0]);  // Prints “12”.
printf("%d\n", A[-1]); // Prints “11”.

The instructions the compiler generates for A[-1] will be correct to calculate the address, whether they use a shift, a multiple, or some other calculation, provided A[-1] is a valid object in the computing model.

Left-shifting a negative number yields a positive number only when there is overflow.

(The C standard specifies behavior in terms of a simple abstract computer where all objects are stored in memory, and every use of an object loads from or stores to its memory. In practice, compilers optimize and may hold objects in registers instead of memory, among other optimizations. The end result of any program with defined behavior should be the same behavior as a program in the abstract model, but the compiler may implement it very differently from how the C standard describes it.)

  • Related