What I ended up doing took at most 0.27s for trial #10.  Since the maximum value is 32767, I just create an array with a structure that stores a list of indexes that have that value:

    typedef struct {
        int indexCount;
        int *indexes; // position (i.e. j) where number is
    } NODE;

Then in my loop, I loop down from the largest possible value to 0, xor it with 'a' to get the value of x to look for.  That is the index into the array of nodes and will tell me quickly which indexes (x<sub>1</sub>..x<sub>N</sub>) contain that number.

    for (largest = 32767; largest > 0; largest--) {
        v = largest ^ a; // value we're looking for
        // see if it has any indexes in range
        for (k = 0; k < nodes[v].indexCount; k++) {
            index = nodes[v].indexes[k];
            if (index >= p && index <=q) {
                found = 1;
                break;
            }
        }
        if (found)
            break;
    }
    printf("%d\n", largest);

This has a couple of notes:

  1. It does more work up front so the number of tests are affected less
  1. It's only viable because of the restriction in values for x and a (0<=x<sub>i</sub><=2<sup>15</sup> and 0<=a<sub>i</sub><=2<sup>15</sup>).  If the possible values were 2<sup>31</sup> it could loop 2 billion times.
  2. It works fastest when the final results are larger.  A random sampling of values in the possible range should be fine but could slow down if the requested range has none of those values.  The poorest results would be a large list of `x` values that match `a` (giving a result of 0)

I think a better solution would be a tree where left means the number has a '0' at that bit and right means the number has a '1' at that bit. The leaves would be the `x` values following that bit pattern.  Each node would maintain the index range where numbers below could be found.  You would walk down the tree using the *opposite* of bits in the `a` value from bit 14 down as long as the node's index range overlaps with p..q.  Structure:

    typedef struct {
        int indexCount;
        int capacity;
        int *indexes;
    } INDEXLIST;

    typedef struct {
        NODE *left, *right;
        int minIndex, maxIndex;
        INDEXLIST indexes;
    } NODE;

When you finally reach the bottom with all 14 bits chosen, those bits make up the number and `indexes` in the node is the list of indexes.