Adding pointer addresses - legality

Question

Since adding two pointers together is illegal, how is this code snippet valid?

struct key *low = &tab[0]; 
struct key *high = &tab[n]; 
struct key *mid; 

while (low < high) 
{ 
  mid = low + (high-low) / 2; //isn't this adding pointers?


//code continues...

The first statement in the while loop seems to add two addresses together, how is this legal?

This code is from K&Rs the C programming language on page 122

Answer 1

The difference of two pointers (high - low) is an integer (actually ptrdiff_t, which is a signed integer type), so you're adding an integer to a pointer, which is perfectly legal. This also explains why it's perfectly OK to divide the difference by 2, which is not something you could do with a pointer.

Answer 2

You are allowed to subtract two pointers(the result is ptrdiff_t) and you are allowed to add an integer value to a pointer. This is covered in the draft C99 standard section 6.5.6 Additive operators paragrph 2:

For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to an object type and the other shall have integer type. (Incrementing is equivalent to adding 1.)

and paragraph 3:

For subtraction, one of the following shall hold:

and includes the following bullets:

both operands are pointers to qualified or unqualified versions of compatible object types; or

Some important notes, when subtracting two pointers they must point to the same array, this is covered in paragraph 9 which says:

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; [...]

In order to avoid undefined behavior the resulting pointer from an addition must still point to the same array or one off the end of the array and if you point to one past the end you shall not dereference it, which is in paragraph 8 which says:

[...]If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.