Sunday 16 January 2011

Bit Vector approach in Java

This is my implementation of the bit vector mentioned in programming pearls. As mentioned in the book the bit vector has execution time and space advantage.1/4th execution time to order a list of 1 million integers in my experiments compared to a quick sort. The execution time was less than a second. The code is self explanatory. May be some more optimization is possible but, this seems ok. The limitation is that, none of the integers repeat in the list plus and integer type is expected for the array index.

An example bit vector representing the numbers 8, 10, 2, 4, 7 is 0010100110100000 with the corresponding bit location set. (0 is inclusive in the list)

/**
 *
 * @author Hari
 */
public class BitVector
{
    //the array of bytes.
   byte[] bitvector;
   //this is the maximum number we expect in the range.
   int nMaxLimit;
   //byte count needed.
   int nByteCount;
   // the zero mask.
   byte byZero = 0x00;
   //byte values used to set and retireve individual bits.
...................
...................
...................
...................
...................

   // Generate the bytes used to set - reset bits in the sequence
   private void genSet()
   {
       bySets[0] = 0x01;
       for(int nIndex = 1; nIndex < 8; nIndex++)
       {
           bySets[nIndex] = (byte) (bySets[nIndex - 1] << 1);
       }//for
   }//

   // Initialize all the bits to zero.
   private void setAllToZero()
   {
       for(int nIndex = 0; nIndex< nByteCount; nIndex++)
       {
           bitvector[nIndex] &= byZero;
       }//for
   }//


   //set the nth bit in the array.
   public void setAt(int n) throws Exception
   {
...................

...................
...................
...................
...................

       locInVector = qt;
       bitvector[locInVector] |= bySets[7 - rem];
          
   }//

   // check if n is in the vector. i.e by checking the nth bit in the byte array.
   public boolean isPresent(int n) throws Exception
   {
       if(n > nMaxLimit || n < 0)
           throw new Exception("Argument outside range of bit vector.");

       int locInVector;
       int qt = n / 8;
       int rem = n % 8;

       locInVector = qt;
       if((bitvector[locInVector] & bySets[7 - rem])==0)
       {
           return false;
       }
       return true;
   }//

...................
...................
...................
...................
...................

}//class


No comments: