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?
数组A[1…n]包含0到n的所有整数，但有一个整数丢失了。在这个问题中， 我们不能直接通过A[i]取得数组中的第i个数。数组A被表示成二进制， 也就是一串的0/1字符，而我们唯一能使用的操作只有“取得A[i]中的第j位”， 这个操作只需要花费常数时间。写程序找出丢失的整数，你能使程序的时间复杂度是O(n)吗？
首先，在这个问题中，明确我们唯一能使用的操作是fetch(a, i, j)即： 取得a[i]中的第j位。它是提供给我们的操作，怎么实现的不用去理它， 而我们要利用它来解决这个问题，并且在我们的程序中，不能使用a[i]这样的操作。
如果我们不能直接使用a[i]，那么我们能利用fetch函数来获得a[i]吗？回答是可以。 数组a中每个元素是一个整型数，所以只要每次取出32位，再计算出它的值即可。
代码如下：
int get(int a[], int i){
int ret = 0;
for(int j=31; j>=0; --j)
ret = (ret << 1) | fetch(a, i, j);
return ret;
}
我们已经通过get(a, i)来取得a[i]的值了，这样一来，我们只需要开一个bool数组， 把出现过的整数标记为true，即可找出丢失的那个整数。
代码如下：
int missing(int a[], int n){
bool *b = new bool[n+1];
memset(b, false, (n+1)*sizeof(bool));
for(int i=0; i<n; ++i)
b[get(a, i)] = true;
for(int i=0; i<n+1; ++i){
if(!b[i]) return i;
}
delete[] b;
}
我们把问题再变难一点点，如果我们能取到的只是数组a中的第j位，即有函数fetch(a, j)， 而不是取到a[i]中的第j位，那又应该怎么做呢。其实也很简单， 计算a[i]需要取出a[i]中的第31位到第0位(共32位)，对应到整个数组上， 就是数组从头开始数起，取出第
32*i+31位到第32*i位，代码如下：int get1(int a[], int i){
int ret = 0;
int base = 32*i;
for(int j=base+31; j>=base; --j)
ret = (ret << 1) | fetch1(a, j);
return ret;
}
public static int fetch(int a[],int i,int j){
return (a[i]>>j)&1;
}
public static int get(int[] a ,int i){
int result = 0 ;
for(int j=31;j>=0;--j){
result = result<<1|fetch(a,i,j);
}
return result ;
}
https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_04_Missing_Number
public class BitInteger {
public static int INTEGER_SIZE;
private boolean[] bits;
public BitInteger() {
bits = new boolean[INTEGER_SIZE];
}
/* Creates a number equal to given value. Takes time proportional
* to INTEGER_SIZE. */
public BitInteger(int value){
bits = new boolean[INTEGER_SIZE];
for (int j = 0; j < INTEGER_SIZE; j++){
if (((value >> j) & 1) == 1) bits[INTEGER_SIZE - 1 - j] = true;
else bits[INTEGER_SIZE - 1 - j] = false;
}
}
/** Returns k-th most-significant bit. */
public int fetch(int k){
if (bits[k]) return 1;
else return 0;
}
/** Sets k-th most-significant bit. */
public void set(int k, int bitValue){
if (bitValue == 0 ) bits[k] = false;
else bits[k] = true;
}
/** Sets k-th most-significant bit. */
public void set(int k, char bitValue){
if (bitValue == '0' ) bits[k] = false;
else bits[k] = true;
}
/** Sets k-th most-significant bit. */
public void set(int k, boolean bitValue){
bits[k] = bitValue;
}
public void swapValues(BitInteger number) {
for (int i = 0; i < INTEGER_SIZE; i++) {
int temp = number.fetch(i);
number.set(i, this.fetch(i));
this.set(i, temp);
}
}
public int toInt() {
int number = 0;
for (int j = INTEGER_SIZE - 1; j >= 0; j--){
number = number | fetch(j);
if (j > 0) {
number = number << 1;
}
}
return number;
}
}
/* Create a random array of numbers from 0 to n, but skip 'missing' */
public static ArrayList<BitInteger> initialize(int n, int missing) {
BitInteger.INTEGER_SIZE = Integer.toBinaryString(n).length();
ArrayList<BitInteger> array = new ArrayList<BitInteger>();
for (int i = 1; i <= n; i++) {
array.add(new BitInteger(i == missing ? 0 : i));
}
// Shuffle the array once.
for (int i = 0; i < n; i++){
int rand = i + (int) (Math.random() * (n-i));
array.get(i).swapValues(array.get(rand));
}
return array;
}
public static int findMissing(ArrayList<BitInteger> array) {
return findMissing(array, BitInteger.INTEGER_SIZE - 1);
}
private static int findMissing(ArrayList<BitInteger> input, int column) {
if (column < 0) { // Base case and error condition
return 0;
}
ArrayList<BitInteger> oneBits = new ArrayList<BitInteger>(input.size()/2);
ArrayList<BitInteger> zeroBits = new ArrayList<BitInteger>(input.size()/2);
for (BitInteger t : input) {
if (t.fetch(column) == 0) {
zeroBits.add(t);
} else {
oneBits.add(t);
}
}
if (zeroBits.size() <= oneBits.size()) {
int v = findMissing(zeroBits, column - 1);
System.out.print("0");
return (v << 1) | 0;
} else {
int v = findMissing(oneBits, column - 1);
System.out.print("1");
return (v << 1) | 1;
}
}
