Find the Missing Number

Suppose you have a list of N-1 integers, and they are from 1-N.
Each number is used at most once.
Therefore, there is a missing number.

To add more complexity, assume you can only look at one bit at any given time.
Let's call this function:

boolean isSet(int index, int bitPosition) { 
   return array[index] & pow(2, bitPosition); 
}

The answer is to view the 0th bit, counting up how many are supposed to be odd
and how many are supposed to be even, we can analyze that the missing number is
in one of these sets, and therefore, one of the sets can be removed completely.
Therefore, the next bit check is reduced from N to N/2, and doing so, will be
something similar to N + N/2 + N/4 + ... smaller than N*lg(N).
The trick is when the number is in the set that is "odd" or that has the bit "set",
then that bit will be set, and you increment and look at the next bit, else, look
at the next bit + 1.

        for (i = 0; i < 8; ++i) { // log(N)
                memset(bitSetList, 0, N);
                memset(bitNotSetList, 0, N);
                bitSet = bitNotSet = 0;
                if (N <= 1) {
                        printf("Printing the value ...\n");
                        printf("%d\n", set);
                        break;
                }
                for (j = 0; j < N; ++j) // N + N/2 + N/4 + ... 
                // Roughly N * lg(N) since 1 + 1/2 + 1/3 + ... + 1/N -> lg(N+1)
                // and N * (1 + 1/2 + ... + 1/N) > N + N/2 + N/4 + ...
                        if (f(array[j], i))
                                bitSetList[bitSet++] = array[j];
                        else
                                bitNotSetList[bitNotSet++] = array[j];

                // Update the index counter.
                if (N%2) {
                        if (N/2 == bitSet)
                                set |= pow(2, i),
                                updateBitSet(&i, &N, bitSet, bitSetList, BIT_SET);
                        else
                                updateBitSet(&i, &N, bitNotSet, bitNotSetList, BIT_NOT_SET);
                } else { // even
                        if (N/2 == bitSet)
                                set |= pow(2, i),
                                updateBitSet(&i, &N, bitSet, bitSetList, BIT_SET);
                        else
                                updateBitSet(&i, &N, bitNotSet, bitNotSetList, BIT_NOT_SET);
                }
        }