What's wrong with my bit vector?

Question

I am trying to create a bit vector backed by an int[].
So I have the following code:

public class BitVector {  

  int[] vector = new int[1 << 16];  

  public void setBit(int nextInt) {  
    nextInt = nextInt & 0xFFFF;  
    int pos = nextInt / 32;  
    int offset = nextInt % 32;  
    vector[pos] |= (1 << offset);    
  }

  public int findClearedBit() {  

    for(int i = 0;  i < vector.length; i++){              
            for(int j = 0; j < 8; j++){  
                if((vector[i] & (1 << j)) == 0)   
            return i * 32 +  j;  
        }  
    }  

    return -1;  
   }  

}  

I know that perhaps I should have used byte[] instead etc but I was wondering why this way it does not work.
The idea is that I pass in int from a stream and keep the lower 16 bits and mark the corresponding bit as set. So when I iterate over the vector I will find the number (indicate by the lower 16 bits) missing.
But I get wrong result. So I believe my handing is wrong.
Any ideas?

Update:
I have a stream of 32-bit integers. As I read them in I try to mark a number missing by using the lower 16-bits and setting the bitvector (code posted).
I also try to find the upper 16 bits missing reading the stream a second time.
So while the missing number is: 231719592 = (1101110011111100001010101000) = (3535-49832) When I read the stream I don't get 49832 as the missing lower bits but 65536

Update2:

public int findMissingInt(File f)throws Exception{  
    Scanner sc = new Scanner(f);  
    int SIZE = 1 << 16; 
    int[] occurences = new int[SIZE];  
    while(sc.hasNext()){  
    occurences[getIdx(sc.nextInt())]++;  
    }  

    int missingUpper = -1;  
    for(int i = 0; i < occurences.length; i++){  
    if(occurences[i] < SIZE){  
        System.out.println("Found upper bits:"+i);  
        missingUpper = i;  
        break;  
    }  
    }
    if(missingUpper == -1){   
    return -1;  
    }  
    //Arrays.fill(occurences, 0);  //I reused this. Bellow changed after answer of Peter de Rivaz 
    BitVector v = new BitVector(new int[1 << (16-5)]);  
    sc = new Scanner(f);
    while(sc.hasNext()){  
    v.setBit(sc.nextInt());  
    }  

    int missingLower = v.findClearedBit();
    System.out.println("Lower bits:"+missingLower);   
    return createNumber(missingUpper, missingLower);  

}   


private int createNumber(int missingUpper, int missingLower) {  
        int result = missingUpper;  
        result = result << 16;  

        return result | missingLower;  
}  



public int getIdx(int nextInt) {          
    return (nextInt >>> 16);        
}    

I get:

Missing number=231719592  
Found upper bits:3535 //CORRECT  
Lower bits:-1  //WRONG
Actual missing number=-1  //WRONG

Answer 1

I think there are two problems:

1. Your array has 65536 entries, but you store 32 bits in each entry, so you only need 65536/32 entries in it.

2. You store 32 bits in each int, but only check j from 0 to 7 when finding gaps

The first bug means that your program reports 65536 as a missing 16bit number. The second bug means that your program does not spot the missing number.

i.e. change

int[] vector = new int[1 << 16];

to

int[] vector = new int[1 << (16-5)];

and change

for(int j = 0; j < 8; j++)

to

for(int j = 0; j < 32; j++)

EDIT

Judging from the comments, the question is actually how to find a missing number with limited RAM. The answer to this question can be found here on stackoverflow.

There is an additional bug in the higher level code.

During the second pass that populates the bitset, you should only include numbers that have the matching upper bits.

i.e. change

v.setBit(sc.nextInt());

to something like

int nx = sc.nextInt();
if (getIdx(nx)==missingUpper)
  v.setBit(nx);