title: What's wrong with my bit vector?
body: <p>I am trying to create a bit vector backed by an <code>int[]</code>.<br>
  So I have the following code:  </p>
  
  <pre><code>public class BitVector {  
  
    int[] vector = new int[1 &lt;&lt; 16];  
  
    public void setBit(int nextInt) {  
      nextInt = nextInt &amp; 0xFFFF;  
      int pos = nextInt / 32;  
      int offset = nextInt % 32;  
      vector[pos] |= (1 &lt;&lt; offset);    
    }
  
    public int findClearedBit() {  
  
      for(int i = 0;  i &lt; vector.length; i++){              
              for(int j = 0; j &lt; 8; j++){  
                  if((vector[i] &amp; (1 &lt;&lt; j)) == 0)   
              return i * 32 +  j;  
          }  
      }  
  
      return -1;  
     }  
  
  }  
  </code></pre>
  
  <p>I know that perhaps I should have used <code>byte[]</code> instead etc but I was wondering why this way it does not work.<br>
  The idea is that I pass in <code>int</code> 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.<br>
  But I get wrong result. So I believe my handing is wrong.<br>
  Any ideas?</p>
  
  <p><strong>Update:</strong><br>
  I have a stream of 32-bit integers. As I read them in I try to mark a number missing by <em>using the lower 16-bits</em> and setting the bitvector (code posted).<br>
  I also try to find the upper 16 bits missing reading the stream a second time.<br>
  So while the missing number is:  <code>231719592</code> = (<code>1101110011111100001010101000</code>)  = (<code>3535</code>-<code>49832</code>)
  When I read the stream I don't get <code>49832</code> as the missing lower bits but <code>65536</code>  </p>
  
  <p><strong>Update2:</strong>   </p>
  
  <pre><code>public int findMissingInt(File f)throws Exception{  
      Scanner sc = new Scanner(f);  
      int SIZE = 1 &lt;&lt; 16; 
      int[] occurences = new int[SIZE];  
      while(sc.hasNext()){  
      occurences[getIdx(sc.nextInt())]++;  
      }  
  
      int missingUpper = -1;  
      for(int i = 0; i &lt; occurences.length; i++){  
      if(occurences[i] &lt; 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 &lt;&lt; (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 &lt;&lt; 16;  
  
          return result | missingLower;  
  }  
  
  
  
  public int getIdx(int nextInt) {          
      return (nextInt &gt;&gt;&gt; 16);        
  }    
  </code></pre>
  
  <p>I get:  </p>
  
  <pre><code>Missing number=231719592  
  Found upper bits:3535 //CORRECT  
  Lower bits:-1  //WRONG
  Actual missing number=-1  //WRONG
  </code></pre>