K&R pointer manipulation

Question

In Chapter 6 of K&R, we go over accessing elements of a structure by pointers. We are given a function:

struct key *binsearch(char *word, struct key *tab, int n)
{
    int cond;
    struct key *low = &tab[0];
    struct key *high = &tab[n];
    struct key *mid;

    while (low < high) {
        mid = low + (high-low) / 2;
        if ((cond = strcmp(word, mid->word)) < 0)
            high = mid;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return NULL;
}

In an earlier version of this program where we weren't using pointers, we could compute mid as mid = (low+high)/2 but now we need to compute mid as mid = low + (high-low) / 2

I understand that you can't add pointers because logically the result doesn't return anything useful, but what I don't understand is aren't we still adding pointers with mid = low + (high-low) / 2? We are adding low to the result of (high-low)/2?

[Read this](http://stackoverflow.com/questions/394767/pointer-arithmetic?rq=1). — WhozCraig, Sep 06 '13 at 15:27

score 0 · Answer 1 · answered Sep 06 '13 at 15:29

0

I figured out my misunderstanding in logic. When you subtract two pointers, the result is the distance between those two pointers, which can be added to a pointer.

answered Sep 06 '13 at 15:29

Shail Patel

1,764
5
30
46

You determine the `offset` from the difference in two pointers. You can then use the address of another pointer as the `base`. In general, when working with pointers, especially arrays, data exists at `BASE + OFFSET`. Good to see you learned from this. – Cloud Sep 06 '13 at 15:47

score 0 · Answer 2 · edited May 23 '17 at 10:25

The pointers in your example are just pointing into an array and so the pointers themselves will be sequentially numbered (increment by 4 or 8 bytes between each element they point to). So subtracting the high pointer from the low give you the range (in bytes) of the array. Divide that by two and then add that onto the base to find the mid point. It's basically the same as doing this by indexing an array.

The more interesting question is why is the mathematical logic reversed to:

mid = low + (high - low)/2; // Dealing with pointers

rather than:

mid = (low + high) /2; // Indexing an array using integers

Quick answer: The C language prohibits adding two pointers GCC Error: Invalid operands to binary +

Longer answer: The problem with the addition (latter approach) is there is a risk of overflowing the maximum range of the datatype. For a 32bit computer (although 16bit was probably the norm when K&R was written) the maximum range of an integer and pointer is +/-2billion and 4Gb respectively.

For indexing an array, it's unlikely that the array will have more than a couple of million entries, so even 10,000,000 + 10,000,000 is not going to result in overflow.

However when dealing with pointers you don't start at 0. You get allocated a block of memory starting at a large number. Depending on the operating system and compiler and particularly if you are dealing with items on the stack, it's entirely possible when adding two pointers you could get overflow in the 32bit range, hence C doesn't allow this and you need to subtract pointers.

And technically the version in K&R for indexing arrays is also broken if you've got an array with more than 1billion elements and you're indexing using unsigned 32bit int. http://googleresearch.blogspot.co.uk/2006/06/extra-extra-read-all-about-it-nearly.html — jmc, Sep 06 '13 at 16:24

score 0 · Answer 3 · answered Sep 06 '13 at 16:20

One way to look at this, is that the calculation is:

 temp = ( high - low ) / 2

temp, an integer value, is half of the distance between the high and low pointers.

 mid = low + temp

mid is the low address plus an offset, temp. temp is NOT a pointer, rather it is an index amount.

Thus, this method does NOT add two pointers.

K&R pointer manipulation

3 Answers3