[11.3] find ONE missing number within four billion integers

1.Example



Bit Vector   

byte[]   =>      byte[0]   byte[1]......

 int arrayIndex = n / 8;    => byte array index

 int bitIndex = n % 8;      => byte array element bit

s= {0,1,3,6}

   index   0 1  2 3 4 5 6  7    
bit array  1 1 0  1 0 0 1 0

bitArray | 1 << (0%8) = 1 0 0  0 0 0 0 0
bitArray | 1 << (1%8) = 1 1 0  0 0 0 0 0
bitArray | 1 << (3%8) = 1 1 0  1 0 0 0 0
bitArray | 1 << (6%8) = 1 1 0  1 0 0 1 0

bitArray & 1 << (6%8) =
1 1 0  1  0 0 "1" 0 & 0 0 0  0  0 0 "1" 0 = 1 ==> 6 exists in bitArray


2. Implementation

// 0                    Store 0
// 1                    Store 1
// .
// .
// .
// 2147483647 = 2^32    Store 2^32
// Assuming we are taking about 32-bit integers. 
// There are 2^32 = 4*10^9 distinct integers.






// Case1: 1GB memory = 1 * 10^9 * 8 bits = 8 billion bits.
// It is enough to use one bit correpresening one distinct integer. 
// We don't need sort 
int radix = 8;
byte[] bitField = new byte[0xffff ffff / radix];// 
void F() throws FileNotFoundException // method had sth to cause this e
{



     Scanner in = new Scanner (new FileReader("a.txt") );
     while (in.hasNextInt())
     {
           int  n = in.hasNextInt();
           int arrayIndex = n / 8;
           int bitIndex = n % 8;
           int setOnePos = 1 << bitIndex;
           bitField[ arrayIndex ] | = setOnePos;
     }



     int arrayLength = bitField.length;
     int bitLength = 8; 





     for (int i = 0 ; i < bitfield.length; i++) {
        for (int j = 0; j < 8; j++) 
        {
           // Retrieves the individual bits of each byte. When 0 bit
           // is found, finds the corresponding value. 
           if ((bitfield[i] & (1 << j)) == 0) {
              System.out.println (i * 8 + j);
              return;
           }
        }
     }

// 0          store integer 0 ~ 2^20      = 0       ~ 1048576*1
// 1          store integer 2^20+1 ~ 2^21 = 1048577 ~ 1048576*2
// .
// .
// .
// 4095       store integer ~ 2^32   =              ~ 1048576*4096 = //                                                  2147483647
// There are 4 billion =2^32 distinct integers 
// one map to one
// >= 2 ^32 bit array = 2^32 / 8 = 2 ^29 byte array


// many map to one

int bitSize  = 1048576;  // 2^20 bits (2^17 bytes)
int blockNum = 4096;    // 2^12
byte[] bitField = new byte[bitSize/8];
int[] blocks    = new int[blockNum];


// function have FileNotFOundExcpetion possibility and throws ... but don't have try and catch
// function have Exception possibility and use try catch 
void findOpenNumber() throws FileNotFoundException
{




     int stating = -1;
     Scanner in = new Scanner ( new FileReader("input_file_q11_4.txt") );

     


     // NOTE: first pass, check which block
     while (in.hasNextInt())
     { 
          int n = in.nextInt();
          blocks[ n / (bitField.length*8)]++;// n/2^20
     }




     for ( int i = 0 ; i < blocks.length ; i++ )
     {
         // Block not fill up, means probably missing a number 
         if (  block[i]  < bitField.length *8 ) // < 2^20
         {
               // If value < 2^20, then at least 1 number is missing
               // in this section
               // In last section: 4095*2^17*8 = 2^32 - 2^20
               // NOTE: ***count the starting integer in that section
               starting = i* bitField.length * 8;
               break;
         }
     }



     // NOTE: second pass, check which specific number from those 2^20 numbers
     in = new Scanner(new FileReader("input_file_q11_4.txt") );
     while (in.hasNextInt())
     {
         int n = in.nextInt();
         // If the number is inside the block that's missing 
         // numbers, we record it
         if ( n >= starting && n < starting + bitField.length *8 )
              bitField[ (n -starting) / 8] |= 1 << ((n-starting)%8) ;
         
     }




     // Find the missing number within those 2^20 integers
     // 2^20 -1 = (2^17-1)*8+7+ 0 = 2^20 -8 +7 +0 
     for (int i = 0; i < bitField.length; i++ )
     {
         for (int j = 0 ; j < 8 ; j++ )
         {
               // Retrieves the individual bits of each byte
               // When 0 bit is found, finds the corresponding value
               if (  bitField[i]  &  (1<





// Bit-vector to store integers
public class BitArray
{
     


    // Field
    private byte[] set;
    // Constructor
    public BitArray (int length)
    {
         arraySize = (length % 8 =! = 0) ? (length / 8 )+1:length / 8;
         this.set = new byte[ arraySize ];
    }




    // Set given number in the bit-array. i.e., make corresponding bit as 1
    public void storeNumber(int number)
    {


         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;

         // so bit at postiion needs to made 1
         this.set[arrayIndex] = (byte)  (this.set[arrayIndex] |  pos );

    }
    private int getArrayIndex(int number )
    {
         return number / 8;
    }
    private int getbitIndex(int number)
    {
         return number % 8;
    }




    // check if the number exists in the array if the corresponding bit is 1, then it exist
    public boolean numberExists(int number)
    {

         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;
         return ( this.set[arrayIndex] & pos ) > 0 ? true:false;       
    }



    private void printSet()
    {
           
    }



    public static void main (String[] args)
    {
           BitArray array = new BitArray(1000);
           System.out.println("length of array:" + array.set.length );


           int num1 = 17;
           array.storeNumber(num1);
           int num2 = 171;
           array.storeNumber(num2);
           int num3 = 400;
           array.storeNumber(num3);


           System.out.println("val "+ num1 + " exists ? " + array.numberExists(num1) );
           System.out.println("val" + num2 + " exists ? " + array.numberExists(num2) );
           System.out.println( "val" + num3 + " exists ? " + array.numberExists(num3) );
           
    }





3. Similar Ones
http://question.ikende.com/question/2D373139353434383837
http://geekrai.blogspot.com/2014/09/bit-array-or-vector.html