Find missing integer in an array with only access to jth bit of element A[i]

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-missing-integer-in-an-array-with-only-access-to-jth-bit-of-elements/.

Problem

An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

Solution
Method 1 - 
I am yet to find the generic solution. Please share if you have any generic solution.

Method 2 - Divide and Conquer approach for array having n=2^k - 1
Let's assume for now that n is 2^k - 1 for some k.
Let's also look at an example where k = 3.

000
001
010
011
100
101
110
111

You'll notice that when there is a full set, like the one shown above, each column (each digit's place) has the same number of ones and zeros. Of course, for convenience we are showing this as sorted, but in reality, I am not stating that it is.

Let's take a look at the following list, where 101 is missing.

000
001
010
011
100
110
111

We look at the first bit of all of the elements ( O(n) ) and figure out which count is less than the other.
We see that for the first bit, there is a number with the 1 in the most significant bit missing. This means that we know that our number has a one in its most significant bit.
Basically, we partition into two sets, one where the most significant bit is 1 and one where the most significant bit is 0. The smaller set shows us what bit the missing number has.

We do the same thing on the smaller partition.

Since it is O(n) + O(n/2) + O (n/4) ... it is basically O (2n) which is O (n).

Here is code

public static int findMissing(ArrayList<Integer> array) {
    return findMissing(array, Integer.SIZE - 1);
}
 
public static int findMissing(ArrayList<Integer> input, int column) {
    if (column < 0) {
        return 0;
    }
    ArrayList<Integer> oddIndices = new ArrayList<Integer>();
    ArrayList<Integer> evenIndices = new ArrayList<Integer>();
    for (Integer t : input) {
        if ((t & (1 << column)) == 0) {
            evenIndices.add(t);
        } else {
            oddIndices.add(t);
        }
    }
    if (oddIndices.size() >= evenIndices.size()) {
        return (findMissing(evenIndices, column - 1)) << 1 | 0;
    } else {
        return (findMissing(oddIndices, column - 1)) << 1 | 1;
    }
}

References
stackoverflow,
stackoverflow,
tian runhe