Matt Chung

A simple C problem

—

by

Matt Chung
in

I’m slowly working through “Computer Systems from a programmer’s perspective” [1] , struggling every bit of the way. I stopped beating myself up about it, though.

The code snippets below are in C. The first function, inplace_swap, swaps two integers. The code itself looks lacks intent but I promise you, it swaps two integers.

The second function, reverses an array. Coming from the Python world, I wondered why in the world we need to pass incount as an additional argument. I discovered the additional argument is absolutely necessary. C functions will always collapse array arguments into a pointer. The length of pointer, which is nothing more than a memory address, cannot be calculated [2].

#include <stdio.h>

void inplace_swap(int *x, int *y){
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void reverse_array(int a[], int cnt){
    int first, last;
    for (first = 0, last = cnt - 1; first <= last; first++, last--){
        inplace_swap(&a[first], &a[last]);
    }

}

This function appears to work just fine, at first. It reverses even numbered array flawlessly, however, fails to reverse an odd numbered array.

void print_array(int a[], int cnt){
    int i;
    for (i=0; i < cnt; i++){
        printf(" %d", a[i]);
    }
    printf("\n");
}

int main(){
    int a[] = {1,2,3,4};
    int a_length = sizeof(a)/sizeof(int);
    printf ("Reversing 1 2 3 4 : ");
    reverse_array(a, a_length);
    print_array(a, a_length);
}

$ ./reverse_array
Reversing 1 2 3 4 :  4 3 2 1

int b[] = {1,2,3,4,5};
int b_length = sizeof(b)/sizeof(int);
printf ("Reversing 1 2 3 4 5:");
reverse_array(b, b_length);
print_array(b, b_length);

$ ./reverse_array
Reversing 1 2 3 4 5: 5 4 0 2 1

3 practice problems

The author reveals there is a bug and poses 3 questions:

  1. For an array of odd length cnt = 2k + 1, what are the values of variables first and last in the final iteration of function reverse_array?
  2. Why does this call to function xor_swap set the array element to 0?
  3. What simple modification to the code for reverse_array would eliminate this problem?

In an odd length array, the variables first and last values are the same. This explains why the middle array element is set to 0. Any number XOR’d with itself will always produce 0. Here are a few examples of XOR’ing two binary values of the same value:

0001 ^ 0001 = 0000
0111 ^ 0111 = 0000

I grew frustrated with the last question. For ten minutes, I held back my impulse to flip to the back of the book and reveal the solution. Instead, I slapped a piece of a piece of paper and a pen onto my desk, and stepped through the each iteration. There’s something about putting the pen to paper, that activates a different part of the brain.

1 2 3 4 5
5 2 3 4 1
5 4 3 2 1

1 2 3 4 5 6 7
7 2 3 4 5 6 1
7 6 3 4 5 2 1
7 6 5 4 3 2 1

The little fix

In an array with odd number of elements, the middle item is always in its final position. We should never call inplace_swapfor the middle item. Instead, we change the condition in the for loop from first <= last to first < last.

Footnotes

[1] My colleague Richard – who graduated from Carnegie Mellon – recommended this book. Its the only book he read from to back, twice.
[2] http://stackoverflow.com/questions/492384/how-to-find-the-sizeofa-pointer-pointing-to-an-array