BitVector (version 2.0, 2010-April-25)

BitVector.py
 
Version: 2.0
 
Author: Avinash Kak (kak@purdue.edu)
 
Date: 2010-April-25
 
 
Download Version 2.0   gztar   bztar 

 
View version 2.0 code in browser 

 

           

Switch to Version 2.0.1




Switch to Version 2.1




Switch to Version 2.2




Switch to Version 3.0   (Version 3.0 works with both Python 2.x and Python 3.x)







 


CHANGE LOG:


 

   Version 2.0

 

       To address the needs of the folks who are using

       the BitVector class in data mining research, the

       new version of the class has been provided with

       several additional methods.  Since the bit

       vectors used by these folks can be extremely

       long, possibly involving millions of bits, the

       new version of the class includes a much faster

       method for counting the total number of set bits

       when a bit vector is sparse.  [But note that this

       new bit counting method may perform poorly for

       dense bit vectors.]  Also for data mining folks,

       the new version of the class is provided with

       similarity and distance calculation metrics such

       as the Jaccard similarity coefficient, Jaccard

       distance, and Hamming distance.  Again for the

       same folks, the class now also has a

       next_set_bit( from_index ) method.  Other

       enhancements to the class include methods for

       folks who do research in cryptography.  Now you

       can directly calculate the greatest common

       divisor of two bit vectors, or find the

       multiplicative inverse of one bit vector modulo

       another bit vector.

 

   Version 1.5.1:

 

       Removed a bug from the implementation of the

       right circular shift operator.

 

   Version 1.5:

 

       This version should prove to be much more

       efficient for long bit vectors.  Efficiency in

       BitVector construction when only its size is

       specified was achieved by eliminating calls to

       _setbit().  The application of logical operators

       to two BitVectors of equal length was also made

       efficient by eliminating calls to the padding

       function.  Another feature of this version is the

       count_bits() method that returns the total number

       of bits set in a BitVector instance.  Yet another

       feature of this version is the setValue() method

       that alters the bit pattern associated with a

       previously constructed BitVector.

   

   Version 1.4.1:

 

       The reset() method now returns 'self' to allow

       for cascaded inovocation with the slicing

       operator.  Also removed the discrepancy between

       the value of the __copyright__ variable in the

       module and the value of license variable in

       setup.py.

 

   Version 1.4:

 

       This version includes the following two upgrades:

       1) code for slice assignment; and 2) A reset

       function to reinitialize a previously constructed

       BitVector.  Additionally, the code was cleaned up

       with the help of pychecker.

 

   Version 1.3.2:

 

       Fixed a potentially misleading documentation

       issue for the Windows users of the BitVector

       class.  If you are writing an internally

       generated BitVector to a disk file, you must open

       the file in the binary mode.  If you don't, the

       bit patterns that correspond to line breaks will

       be misinterpreted.  On a Windows machine in the

       text mode, the bit pattern 000001010 ('\n') will

       be written out to the disk as 0000110100001010

       ('\r\n').

 

   Version 1.3.1:

 

       Removed the inconsistency in the internal

       representation of bit vectors produced by logical

       bitwise operations vis-a-vis the bit vectors

       created by the constructor.  Previously, the

       logical bitwise operations resulted in bit

       vectors that had their bits packed into lists of

       ints, as opposed to arrays of unsigned shorts.

 

   Version 1.3:

 

       (a) One more constructor mode included: When

       initializing a new bit vector with an integer

       value, you can now also specify a size for the

       bit vector.  The constructor zero-pads the bit

       vector from the left with zeros. (b) The

       BitVector class now supports 'if x in y' syntax

       to test if the bit pattern 'x' is contained in

       the bit pattern 'y'.  (c) Improved syntax to

       conform to well-established Python idioms. (d)

       What used to be a comment before the beginning of

       each method definition is now a docstring.

 

   Version 1.2:

 

       (a) One more constructor mode included: You can

       now construct a bit vector directly from a string

       of 1's and 0's.  (b) The class now constructs a

       shortest possible bit vector from an integer

       value.  So the bit vector for the integer value 0

       is just one bit of value 0, and so on. (c) All

       the rich comparison operators are now

       overloaded. (d) The class now includes a new

       method 'intValue()' that returns the unsigned

       integer value of a bit vector.  This can also be

       done through '__int__'. (e) The package now

       includes a unittest based framework for testing

       out an installation.  This is in a separate

       directory called "TestBitVector".

   

   Version 1.1.1:

 

       The function that does block reads from a disk

       file now peeks ahead at the end of each block to

       see if there is anything remaining to be read in

       the file.  If nothing remains, the more_to_read

       attribute of the BitVector object is set to

       False.  This simplifies reading loops. This

       version also allows BitVectors of size 0 to be

       constructed

 

 

   Version 1.1:

 

       I have changed the API significantly to provide

       more ways for constructing a bit vector.  As a

       result, it is now necessary to supply a keyword

       argument to the constructor.

   

 

 


INSTALLATION:


 

   The BitVector class has been packaged using

   Distutils.  For installation, execute the following

   command-line in the source directory (this is the

   directory that contains the setup.py file after you

   have downloaded and uncompressed the package):

 

       python setup.py install

 

   You have to have root privileges for this to work.

   On Linux distributions, this will install the module

   file at a location that looks like

 

        /usr/lib/python2.6/site-packages/

 

   If you do not have root access, you have the option

   of working directly off the directory in which you

   downloaded the software by simply placing the

   following statements at the top of your scripts that

   use the BitVector class

 

       import sys

       sys.path.append( "pathname_to_BitVector_directory" )

 

   To uninstall the module, simply delete the source

   directory, locate where BitVector was installed with

   "locate BitVector" and delete those files.  As

   mentioned above, the full pathname to the installed

   version is likely to look like

   /usr/lib/python2.6/site-packages/BitVector*

 

   If you want to carry out a non-standard install of

   BitVector, look up the on-line information on

   Disutils by pointing your browser to

 

          http://docs.python.org/dist/dist.html

 

 

 

 


INTRODUCTION:


 

   The BitVector class for a memory-efficient packed

   representation of bit arrays and for logical

   operations on such arrays.  The core idea used in

   this Python script for bin packing is based on an

   internet posting by Josiah Carlson to the Pyrex

   mailing list.

 

   Operations supported on bit vectors:

 

          __getitem__

          __setitem__

          __len__

          __iter__

          __contains__

          __getslice__

          __str__

          __int__

          __add__

          __eq__, __ne__, __lt__, __le__, __gt__, __ge__

          |            for bitwise or

          &            for bitwise and              

          ^            for bitwise xor

          ~            for bitwise inversion

          <<           for circular rotation to the left

          >>           for circular rotation to the right

          +            for concatenation

          intValue()   for returning the integer value 

          divide_into_two

          permute

          unpermute

          pad_from_left

          pad_from_right

          read_bits_from_file

          write_to_file

          read_bits_from_fileobject

          write_bits_to_fileobject

          reset

          slice assignment

          setValue

          count_bits

          count_bit_sparse          

          jaccard_similarity

          jaccard_distance

          hamming_distance

          next_set_bit

          rank_of_bit_set_at_index

          isPowerOf2

          isPowerOf2_sparse

          reverse

          gcd

          multiplicative_inverse

 

 

 


CONSTRUCTING BIT VECTORS:


 

 

    You can construct a bit vector in seven different ways.

 

    (1) You can construct a bit vector directly from

        either a tuple or a list of bits, as in

 

           bv =  BitVector( bitlist = [1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1] ) 

 

    (2) You can construct a bit vector from an integer by

 

           bv =  BitVector( intVal = 56789 )

 

        The bits stored now will correspond to the

        binary representation of the integer.  The

        resulting bit vector is the shortest possible

        bit vector for the integer value supplied.  For

        example, when intVal is 0, the bit vector

        constructed will consist of just the bit 0.

 

 

    (3) When initializing a bit vector with an intVal as

        shown above, you can also specify a size for the

        bit vector:

 

           bv = BitVector( intVal = 0, size = 8 )

 

        will return the bit vector consisting of the bit

        pattern 00000000.  The zero padding needed for

        meeting the size requirement is always on the

        left.  If the size supplied is smaller than what

        it takes to create the shortest possible bit

        vector for intVal, an exception is thrown.

 

            

    (4) You can create a zero-initialized bit vector of

        a given size by

 

           bv  = BitVector( size = 62 )

 

        This bit vector will hold exactly 62 bits, all

        initialized to the 0 bit value.

 

    (5) You can construct a bit vector from a disk file

        by a two-step procedure. First you construct an

        instance of bit vector by

 

           bv  =  BitVector( filename = 'somefile' )   

 

        This bit vector itself is incapable of holding

        the bits.  To now create bit vectors that

        actually hold the bits, you need to make the

        following sort of a call on the above variable

        bv:

 

           bv1 =  bv.read_bits_from_file( 64 )    

 

        bv1 will be a regular bit vector containing 64

        bits from the disk file. If you want to re-read

        a file from the beginning for some reason, you

        must obviously first close the file object that

        was acquired with a call to the BitVector

        constructor with a filename argument.  This can

        be accomplished by

 

          bv.close_file_object()

 

    (6) You can construct a bit vector from a string of

        1's and 0's by

 

           bv  =  BitVector( bitstring = '110011110000' )      

 

    (7) Yet another way to construct a bit vector is to

        read the bits directly from a file-like object,

        as in

 

           x = "111100001111"

           fileobj = StringIO.StringIO( x )

           bv = BitVector( fp = fileobj )

 

 

 


OPERATIONS SUPPORTED BY THE BITVECTOR CLASS:


 


DISPLAYING BIT VECTORS:


 

 

    1) Since the BitVector class implements the __str__

       method, a bit vector can be displayed on a

       terminal by

 

              print bitvec

 

       Basically, you can always obtain the string

       representation of a bit vector by

 

              str( bitvec )

 

       and integer value by

 

              int( bitvec )

 

 

 


ACCESSING AND SETTING INDIVIDUAL BITS AND SLICES:


 

 

    2) Any single bit of a bit vector bv can be set to 1

       or 0 by

 

              bv[M] = 1_or_0

              print bv[M]

 

       for accessing (and setting) the bit at the

       position that is indexed M.  You can retrieve the

       bit at position M by bv[M].  Note that the index

       0 corresponds to the first bit at the left end of

       a bit pattern.

 

    3) A slice of a bit vector obtained by

 

              bv[i:j]

 

        is a bit vector constructed from the bits at index positions

        from i through j-1.

 

    4) You can also carry out slice assignment:

 

              bv1 = BitVector( size = 25 )

              bv2 = BitVector( bitstring = '1010001' )

              bv1[6:9]  = bv2[0:3]

              bv3 = BitVector( bitstring = '101' )                 

              bv1[0:3]  = bv3

 

       The first slice assignment will set the 6th, 7th,

       and the 8th bits of the bit vector bv1 according

       to the first three bits of bv2.  The second slice

       assignment will set the first three bits of bv1

       according to the three bits in bv3.

 

    5) You can iterate over a bit vector, as illustrated

       by

 

              for bit in bitvec:

                  print bit,   

 

       This is made possible by the override definition

       for the special __iter__() method.

 

    6) Negative subscripts for array-like indexing are

       supported.  Therefore,

 

              bitvec[ -i ]

 

       is legal assuming that the index range is not

       violated.  A negative index carried the usual

       Python interpretation: The last element of a bet

       vector is indexed -1 and the first element -(n+1)

       if n is the total number of bits in the bit

       vector.

 

    7) You can reset a previously constructed bit vector

       to either the all zeros state or the all ones

       state by

 

              bv1 = BitVector( size = 25 )

              ...

              ...

              bv1.reset( 1 )

              ...

              ...

              bv1.reset( 0 )

 

       The first call to reset() will set all the bits

       of bv1 to 1's and the second call all bit to 0's.

 

 

 


LOGICAL OPERATIONS ON BIT VECTORS:


 

 

    8) Given two bit vectors bv1 and bv2, you can

       perform bitwise logical operations on them by

 

              result_bv  =  bv1 ^ bv2           # for bitwise XOR

              result_bv  =  bv1 & bv2           # for bitwise AND

              result_bv  =  bv1 | bv2           # for bitwise OR

              result_bv  =  ~bv1                # for bitwise negation

 

 

 


COMPARING BIT VECTORS:


 

    9) Given two bit vectors bv1 and bv2, you can carry

       out the following comparisons that return Boolean

       values:

 

              bv1 ==  bv2

              bv1 !=  bv2

              bv1 <   bv2

              bv1 <=  bv2

              bv1 >   bv2

              bv1 >=  bv2

 

       The equalities and inequalities are determined by

       the integer values associated with the bit

       vectors.

 

 

 

 


OTHER SUPPORTED OPERATIONS:


 

 

   10) You can permute and un-permute bit vectors:

 

              bv_permuted   =  bv.permute( permutation_list )

 

              bv_unpermuted =  bv.unpermute( permutation_list )

 

 

   11) Left and right circular rotations can be carried

       out by

 

              bitvec  << N 

 

              bitvec  >> N

 

       for circular rotations to the left and right by N bit

       positions.

 

 

   12) A bit vector containing an even number of bits

       can be divided into two equal parts by

 

              [left_half, right_half] = bitvec.divide_into_two()

 

       where left_half and right_half hold references to the two

       returned bit vectors.

 

 

   13) You can find the integer value of a bit array by

 

              bitvec.invValue()

 

       or by

 

              int( bitvec )

 

 

   14) You can convert a bit vector into its string

       representation by

 

              str( bitvec )

 

 

   15) Because __add__ is supplied, you can always join

       two bit vectors by

 

              bitvec3  =  bitvec1  +  bitvec2

 

       bitvec3 is a new bit vector that contains all the

       bits of bitvec1 followed by all the bits of

       bitvec2.

 

         

   16) You can write a bit vector directly to a file, as

       illustrated by the following example that reads

       one bit vector from a file and then writes it to

       another file

 

              bv = BitVector( filename = 'input.txt' )

              bv1 = bv.read_bits_from_file(64)        

              print bv1           

              FILEOUT = open( 'output.bits', 'wb' )

              bv1.write_to_file( FILEOUT )

              FILEOUT.close()

              bv = BitVector( filename = 'output.bits' )

              bv2 = bv.read_bits_from_file( 64 )

              print bv2

 

         IMPORTANT: The size of bit vector must be a

                     multiple of of 8 for this write

                     function to work.  If this

                     condition is not met, the function

                     throws an exception.

 

         IMPORTANT FOR WINDOWS USERS: When writing an

                     internally generated bit vector out

                     to a disk file, it is important to

                     open the file in the binary mode as

                     shown.  Otherwise, the bit pattern

                     00001010 ('\n') in your bitstring

                     will be written out as

                     0000110100001010 ('\r\n'), which

                     is the linebreak on Windows

                     machine.

 

   17) You can also write a bit vector directly to a

       stream object, as illustrated by

 

              fp_write = StringIO.StringIO()

              bitvec.write_bits_to_fileobject( fp_write )

              print fp_write.getvalue()         # 111100001111 

         

 

   18) You can pad a bit vector from the left or from

       the right with a designated number of zeros

 

              bitvec.pad_from_left( n )

 

              bitvec.pad_from_right( n )

 

       In the first case, the new bit vector will be the

       same as the old bit vector except for the

       additional n zeros on the left.  The same thing

       happens in the second case except that now the

       additional n zeros will be on the right.

 

   19) You can test if a bit vector x is contained in

       another bit vector y by using the syntax 'if x in

       y'.  This is made possible by the override

       definition for the special __contains__() method.

 

   20) You can count the number of bits set in a

       BitVector instance by

 

          bv = BitVector( bitstring = '100111' )

          print bv.count_bits()                     # 4

 

   21) You can change the bit pattern associated with a

       previously constructed BitVector instance:

 

          bv = BitVector( intVal = 7, size =16 )

          print bv                              # 0000000000000111

          bv.setValue( intVal = 45 )

          print bv                              # 101101

 

   22) For folks who use bit vectors with millions of

       bits in them but with only a few bits set, your

       bit counting will go much, much faster if you

       call count_bits_sparse() instead of count_bits():

 

          # a BitVector with 2 million bits:

          bv = BitVector( size = 2000000 )

          bv[345234] = 1

          bv[233]=1

          bv[243]=1

          bv[18]=1

          bv[785] =1

          print bv.count_bits_sparse()

          

   23) You can calculate similarity and distance between

       two bit vectors using the Jaccard similarity

       coefficient and the Jaccard distance.  Also, you

       can calculate the Hamming distance between two

       bit vectors:

 

          bv1 = BitVector( bitstring = '11111111' )

          bv2 = BitVector( bitstring = '00101011' )

          print bv1.jaccard_similarity( bv2 )

          print bv1.jaccard_distance( bv2 )

          print bv1.hamming_distance( bv2 )

 

   24) Starting from a given bit position, you can find

       the position index of the next set bit:

 

          bv = BitVector( bitstring = '00000000000001' )

          print bv.next_set_bit( 5 ) 

 

   25) You can measure the "rank" of a bit that is set

       at a given position.  Rank is the number of bits

       that are set up to the position of the bit you

       are interested in.

 

          bv = BitVector( bitstring = '00000000000001' )

          print bv.next_set_bit( 5 )      

 

   26) You can test whether the integer value of a bit

       vector is a power of two.  The sparse version of

       this method will work much faster for very long

       bit vectors.  However, the regular version may

       work faster for small bit vectors.

 

          bv = BitVector( bitstring = '10000000001110' )

          print bv.isPowerOf2()

          print bv.isPowerOf2_sparse()

 

   27) Given a bit vector, you can construct a bit

       vector with all the bits reversed, in the sense

       that what was left to right before now becomes

       right to left.

 

          bv = BitVector( bitstring = '0001100000000000001' )

          print bv.reverse()

 

   28) You can find the greatest common divisor of two

       bitvectors:

 

          bv1 = BitVector( bitstring = '01100110' )

          bv2 = BitVector( bitstring = '011' ) 

          bv = bv1.gcd( bv2 )

          print int(bv)

 

   29) You can find the multiplicative inverse of a bit

       vector vis-a-vis a given modulus:

 

          bv_modulus = BitVector( intVal = 32 )

          bv = BitVector( intVal = 17 ) 

          bv_result = bv.multiplicative_inverse( bv_modulus )

          if bv_result is not None:

              print int(bv_result)

          else: print "No multiplicative inverse in this case"

 

 

 


HOW THE BIT VECTORS ARE STORED:


 

    The bits of a bit array are stored in 16-bit

    unsigned ints.  After resolving the argument with

    which the constructor is called (which happens in

    lines (A2) through (A70) of the file BitVector.py),

    the very first thing that the constructor does is to

    figure out in line (A78) as to how many of those

    2-byte ints it needs for the bits.  For example, if

    you wanted to store a 64-bit array, the variable

    'two_byte_ints_needed' in line (A78) would be set to

    4. (This does not mean that the size of a bit vector

    must be a multiple of 16.  Any sized bit vectors can

    constructed using the required number of two-byte

    ints.) Line (A79) then creates an array of 2-byte

    ints and initializes it with the required number of

    zeros.  Lines (A80) then shifts the bits into the

    array of two-byte ints.

 

    As mentioned above, note that it is not necessary

    for the size of the vector to be a multiple of 16

    even though we are using C's unsigned short as as a

    basic unit for storing the bit arrays.  The class

    BitVector keeps track of the actual number of bits

    in the bit vector through the "size" instance

    attribute.

 

    With regard to the code in lines (A2) through (A77)

    of the file BitVector.py, note that, except for one

    case, the constructor must be called with a single

    keyword argument, which determines how the bit

    vector will be constructed.  The single exception to

    this rule is for the keyword argument 'intVal' which

    can be used along with the 'size' keyword argument.

    When 'intVal' is used with the 'size' option, the

    bit vector constructed for the integer is the

    shortest possible bit vector.  On the other hand,

    when 'size' is also specified, the bit vector is

    padded with zeroes from the left so that it has the

    specified size.

 

    Lines (A16) through (A22) are for the following sort

    of a call

 

           bv = BitVector( filename = 'myfilename' )

 

    This call returns a bit vector on which you must

    subsequently invoke the 'read_bits_from_file()'

    method to actually obtain a bit vector consisting of

    the bits that constitute the information stored in

    the file.

 

    Lines (A23) through (A28) are for the case when you

    want to construct a bit vector by reading the bits

    off a file-like object, as in

 

          x = "111100001111"

          fileobj = StringIO.StringIO( x )

          bv = BitVector( fp = fileobj )

 

    Lines (A29) through (A61) are for the case when you

    want to construct a bit vector from an integer, as

    in

 

          bv = BitVector( intVal = 123456 )

 

    The bits stored in the bit vector will correspond to

    the binary representation of the integer argument

    provided.  The bit vector constructed with the above

    call will be the shortest possible bit vector for

    the integer supplied.  As a case in point, when the

    intVal is 0, the bit vector will consist of a single

    bit which will be 0 also.  The code in lines (A29)

    through (A61) can also handle the following sort of

    a call

 

          bv = BitVector( intVal = 46, size = 16 )        

 

    which returns a bit vector of a specfic size by

    padding the shortest possible bit vector the the

    intVal with zeros from the left.

    

    Lines (A62) through (A68) are for constructing a bit

    vector with just the size information, as in

 

          bv = BitVector( size = 61 )

 

    This returns a bit vector that will hold exactly 61

    bits, all initialized to the zero value.

 

    Lines (A69) through (A73) are for constructing a bit

    vector from a bitstring, as in

 

          bv = BitVector( bitstring = '00110011111' )

 

    Finally, lines (A74) through (A77) are for

    constructing a bit vector from a list or a tuple of

    the individual bits:

      

          bv = BitVector( bitlist = (1, 0, 1, 1, 0, 0, 1) )

 

    The bit vector constructed is initialized with the

    supplied bits.

 

 

 


ACKNOWLEDGEMENTS:


 

    The author is grateful to Oleg Broytmann for

    suggesting many improvements that were incorporated

    in Version 1.1 of this package.  The author would

    like to thank Kurt Schwehr whose email resulted in

    the creation of Version 1.2.  Kurt also caught an

    error in my earlier version of 'setup.py' and

    suggested a unittest based approach to the testing

    of the package.  Kurt also supplied the Makefile

    that is included in this distribution.  The author

    would also like to thank all (Scott Daniels, Blair

    Houghton, and Steven D'Aprano) for their responses

    to my comp.lang.python query concerning how to make

    a Python input stream peekable.  This feature was

    included in Version 1.1.1.

 

    With regard to the changes incorporated in Version

    1.3, thanks are owed to Kurt Schwehr and Gabriel

    Ricardo for bringing to my attention the bug related

    to the intVal method of initializing a bit vector

    when the value of intVal exceeded sys.maxint. This

    problem is fixed in Version 1.3.  Version 1.3 also

    includes many other improvements that make the

    syntax better conform to the standard idioms of

    Python.  These changes and the addition of the new

    constructor mode (that allows a bit vector of a

    given size to be constructed from an integer value)

    are also owing to Kurt's suggestions.

 

    With regard to the changes incorporated in Version

    1.3.1, I would like to thank Michael Haggerty for

    noticing that the bitwise logical operators resulted

    in bit vectors that had their bits packed into lists

    of ints, as opposed to arrays of unsigned shorts.

    This inconsistency in representation has been

    removed in version 1.3.1.  Michael has also

    suggested that since BitVector is mutable, I should

    be overloading __iand__(), __ior__(), etc., for

    in-place modifications of bit vectors.  Michael

    certainly makes a good point. But I am afraid that

    this change will break the code for the existing

    users of the BitVector class.

 

    I thank Mathieu Roy for bringing to my attention the

    problem with writing bitstrings out to a disk files

    on Windows machines.  This turned out to be a

    problem more with the documentation than with the

    BitVector class itself.  On a Windows machine, it is

    particularly important that a file you are writing a

    bitstring into be opened in binary mode since

    otherwise the bit pattern 00001010 ('\n') will be

    written out as 0000110100001010 ('\r\n').  This

    documentation fix resulted in Version 1.3.2.

 

    With regard to Version 1.4, the suggestions/bug

    reports made by John Kominek, Bob Morse, and Steve

    Ward contributed to this version.  I wish to thank

    all three. John wanted me to equip the class with a

    reset() method so that a previously constructed

    class could be reset to either all 0's or all

    1's. Bob spotted loose local variables in the

    implementation --- presumably left over from a

    debugging phase of the code.  Bob recommended that I

    clean up the code with pychecker. That has been

    done.  Steve noticed that slice assignment was not

    working.  It should work now.

 

    Version 1.4.1 was prompted by John Kominek

    suggesting that if reset() returned self, then the

    slice operation could be combined with the reset

    operation.  Thanks John!  Another reason for 1.4.1

    was to remove the discrepancy between the value of

    the __copyright__ variable in the module and the

    value of license variable in setup.py.  This

    discrepancy was brought to my attention by David

    Eyk.  Thanks David!

 

    Version 1.5 has benefited greatly by the suggestions

    made by Ryan Cox.  By examining the BitVector

    execution with cProfile, Ryan observed that my

    implementation was making unnecessary method calls

    to _setbit() when just the size option is used for

    constructing a BitVector instance.  Since Python

    allocates cleaned up memory, it is unnecessary to

    set the individual bits of a vector if it is known

    in advance that they are all zero. Ryan made a

    similar observation for the logical operations

    applied to two BitVector instances of equal length.

    He noticed that I was making unnecessary calls to

    _resize_pad_from_left() for the case of equal

    arguments to logical operations.  Ryan also

    recommended that I include a method that returns the

    total number of bits set in a BitVector instance.

    The new method count_bits() does exactly

    that. Thanks Ryan for all your suggestions.  Version

    1.5 also includes the method setValue() that allows

    the internally stored bit pattern associated with a

    previously constructed BitVector to be changed.  A

    need for this method was expressed by Aleix

    Conchillo.  Thanks Aleix.

    

    Version 1.5.1 is a quick release to fix a bug in the 

    right circular shift operator.  This bug was discovered

    by Jasper Spaans.  Thanks very much Jasper.

 

    Version 2.0 was prompted mostly by the needs of

    folks who play with very long bit vectors that can

    consist of millions of bits.  I believe such bit

    vectors are encountered in data mining research and

    development.  Towards that end, amongst the new

    methods in Version 2, the count_bits_sparse() was

    provided by Rhiannon.  She says when a bit vector

    contains over 2 million bits and only, say, five

    bits are set, her method is faster than the older

    count_bits() method by a factor of roughly 18.

    Thanks Rhiannon. [The logic of the new

    implementation works best for very sparse bit

    vectors.  For very dense vectors, it may perform

    more slowly than the regular count_bits() method.

    For that reason, I have retained the original

    method.]  Rhiannon's implementation is based on what

    has been called the Kernighan way at the web site

    http://graphics.stanford.edu/~seander/bithacks.html.

    Version 2 also includes a few additional functions

    posted at this web site for extracting information

    from bit fields.  Also included in this new version

    is the next_set_bit() method supplied by Jason Allum.

    I believe this method is also useful for data mining

    folks.  Thanks Jason.  Additional methods in Version

    2 include the similarity and distance metrics for

    comparing two bit vectors, methods for finding the

    greatest common divisor of two bit vectors, and a

    method that determines the multiplicative inverse of

    a bit vector vis-a-vis a modulus.  These last two

    methods should prove useful to folks in

    cryptography.

    

 

 


ABOUT THE AUTHOR:


 

    Avi Kak is the author of "Programming with Objects:

    A Comparative Presentation of Object-Oriented

    Programming with C++ and Java", published by

    John-Wiley in 2003. This book presents a new

    approach to the combined learning of two large

    object-oriented languages, C++ and Java.  It is

    being used as a text in a number of educational

    programs around the world.  This book has also been

    translated into Chinese.  Avi Kak is also the author

    of "Scripting with Objects: A Comparative

    Presentation of Object-Oriented Scripting with Perl

    and Python," published in 2008 by John-Wiley.

 

 

 


SOME EXAMPLE CODE:


 

    #!/usr/bin/env python

    import BitVector

 

    # Construct a bit vector from a list or tuple of bits:

    bv = BitVector.BitVector( bitlist = (1, 0, 0, 1) )

    print bv                                # 1001

 

    # Construct a bit vector from an integer:

    bv = BitVector.BitVector( intVal = 5678 )

    print bv                                # 0001011000101110

 

    # Construct a bit vector of a given size from a given

    # integer:

    bv = BitVector( intVal = 45, size = 16 )

    print bv                                # 0000000000101101

 

    # Construct a zero-initialized bit vector of a given size:

    bv = BitVector.BitVector( size = 5 )

    print bv                                # 00000

 

    # Construct a bit vector from a bit string:

    bv = BitVector.BitVector( bitstring = '110001' )     

    print bv[0], bv[1], bv[2], bv[3], bv[4], bv[5]       # 1 1 0 0 0 1

    print bv[-1], bv[-2], bv[-3], bv[-4], bv[-5], bv[-6] # 1 0 0 0 1 1

 

    # Construct a bit vector from a file like object:

    import StringIO

    x = "111100001111"

    fp_read = StringIO.StringIO( x )

    bv = BitVector.BitVector( fp = fp_read )

    print bv                                    # 111100001111 

 

    # Experiments with bitwise logical operations:

    bv3 = bv1 | bv2                              

    bv3 = bv1 & bv2

    bv3 = bv1 ^ bv2

    bv6 = ~bv5

 

    # Find the length of a bit vector

    print len( bitvec )

 

    # Find the integer value of a bit vector

    print int( bitvec )

 

    # Open a file for reading bit vectors from

    bv = BitVector.BitVector( filename = 'TestBitVector/testinput1.txt' )

    print bv                                    # nothing yet

    bv1 = bv.read_bits_from_file(64)    

    print bv1                            # first 64 bits from the file

 

    # Divide a bit vector into two equal sub-vectors:

    [bv1, bv2] = bitvec.divide_into_two()

 

    # Permute and Un-Permute a bit vector:

    bv2 = bitvec.permute( permutation_list )

    bv2 = bitvec.unpermute( permutation_list )

 

    # Try circular shifts to the left and to the right

    bitvec << 7

    bitvec >> 7

 

    # Try 'if x in y' syntax for bit vectors:

    bv1 = BitVector( bitstring = '0011001100' )

    bv2 = BitVector( bitstring = '110011' )

    if bv2 in bv1:

        print "%s is in %s" % (bv2, bv1)

    else:

        print "%s is not in %s" % (bv2, bv1)

 

    .....

    .....

 


    (For a more complete working example, see the

     example code in the BitVectorDemo.py file in the

     Examples sub-directory.)








 

Modules

    

       

array

operator







 

Classes

    

       



BitVectorIterator

__builtin__.object





BitVector






 





 

class BitVector(__builtin__.object)

    

    
Methods defined here:


__add__(self, other)
Concatenate the argument bit vector with the bit

vector on which the method is invoked.  Return the

concatenated bit vector as a new BitVector object.



__and__(self, other)
Take a bitwise 'and' of the bit vector on which the method is

invoked with the argument bit vector.  Return the result as a

new bit vector.  If the two bit vectors are not of the same

size, pad the shorter one with zeros from the left.



__contains__(self, otherBitVec)
This supports 'if x in y' and 'if x not in y'

syntax for bit vectors.



__eq__(self, other)



__ge__(self, other)



__getitem__ = _getbit(self, posn)



__getslice__(self, i, j)
Allow slicing with [i:j], [:], etc.



__gt__(self, other)



__init__(self, *args, **kwargs)



__int__ = intValue(self)



__invert__(self)
Invert the bits in the bit vector on which the

method is invoked and return the result as a new

bit vector.



__iter__(self)
To allow iterations over a bit vector by supporting the

'for bit in bit_vector' syntax:



__le__(self, other)



__len__ = _getsize(self)



__lshift__(self, n)
For an in-place left circular shift by n bit positions



__lt__(self, other)



__ne__(self, other)



__or__(self, other)
Take a bitwise 'or' of the bit vector on which the

method is invoked with the argument bit vector.  Return

the result as a new bit vector.  If the two bit vectors

are not of the same size, pad the shorter one with

zero's from the left.



__rshift__(self, n)
For an in-place right circular shift by n bit positions.



__setitem__(self, pos, item)
This is needed for both slice assignments and for 

index assignments.  It checks the types of pos and item

to see if the call is for slice assignment.  For slice

assignment, pos must be of type 'slice' and item of 

type BitVector.  For index assignment, the argument types

are checked in the _setbit() method.



__str__(self)
To create a print representation



__xor__(self, other)
Take a bitwise 'xor' of the bit vector on which

the method is invoked with the argument bit vector.

Return the result as a new bit vector.  If the two

bit vectors are not of the same size, pad the shorter

one with zeros from the left.



circular_rot_left(self)
This is merely another implementation of the method

circular_rotate_left_by_one() shown above.  This one

does NOT use map functions.  This method carries out a

one-bit left circular shift of a bit vector.



circular_rot_right(self)
This is merely another implementation of the method

circular_rotate_right_by_one() shown above.  This one

does NOT use map functions.  This method does a one-bit

right circular shift of a bit vector.



circular_rotate_left_by_one(self)
For a one-bit in-place left circular shift



circular_rotate_right_by_one(self)
For a one-bit in-place right circular shift



close_file_object(self)
For closing a file object that was used for reading

the bits into one or more BitVector objects.



count_bits(self)
Return the number of bits set in a BitVector instance.



count_bits_sparse(self)
For sparse bit vectors, this method, contributed by 

Rhiannon, will be much faster.  She estimates that 

if a bit vector with over 2 millions bits has only 

five bits set, this will return the answer in 1/18

of the time taken by the count_bits() method.  Note

however, that count_bits() may work much faster for

dense-packed bit vectors.  Rhianon's implementation 

is based on an algorithm generally known as the

Brian Kernighan's way, although its antecedents 

predate its mention by Kernighan and Ritchie.



divide_into_two(self)
Divides an even-sized bit vector into two and returns

the two halves as a list of two bit vectors.



gcd(self, other)
Using Euclid's Algorithm, returns the greatest

common divisor of the integer value of the bit

vector on which the method is invoked and the

integer value of the argument bit vector.



hamming_distance(self, other)
Computes the Hamming distance between two bit vectors



intValue(self)
Return the integer value of a bitvector



isPowerOf2(self)
Determines whether the integer value of a bit vector is

a power of 2.



isPowerOf2_sparse(self)
Faster version of isPowerOf2() for sparse bit vectors



jaccard_distance(self, other)
Computes the Jaccard distance between two bit vectors



jaccard_similarity(self, other)
Computes the Jaccard similarity coefficient

between two bit vectors



multiplicative_inverse(self, modulus)
Calculates the multiplicative inverse of a bit 

vector modulo the bit vector that is supplied as the

argument. Code based on the Extended Euclid's 

Algorithm.



next_set_bit(self, from_index=0)
This method, contributed by Jason Allum, calculates

the number of bit positions from the current

position index to the next set bit.



pad_from_left(self, n)
Pad a bit vector with n zeros from the left



pad_from_right(self, n)
Pad a bit vector with n zeros from the right



permute(self, permute_list)
Permute a bit vector according to the indices

shown in the second argument list.  Return the

permuted bit vector as a new bit vector.



rank_of_bit_set_at_index(self, position)
For a bit that is set at the argument 'position',

this method returns how many bits are set to the 

left of that bit.  For example, in the bit pattern

000101100100, a call to this method with position

set to 9 will return 4.



read_bits_from_file(self, blocksize)
Read blocksize bits from a disk file and return a

BitVector object containing the bits.  If the file

contains fewer bits than blocksize, construct the

BitVector object from however many bits there are

in the file.  If the file contains zero bits, return

a BitVector object of size attribute set to 0.



read_bits_from_fileobject(self, fp)
This function is meant to read a bit string from a 

file like object.



reset(self, val)
Resets a previously created BitVector to either all

zeros or all ones depending on the argument val.

Returns self to allow for syntax like

       bv = bv1[3:6].reset(1)

or

       bv = bv1[:].reset(1)



reverse(self)
Returns a new bit vector by reversing the bits in the

bit vector on which the method is invoked.



setValue(self, *args, **kwargs)
Changes the bit pattern associated with a previously

constructed BitVector instance.  The allowable modes

for chaning the internally stored bit patten are the

same as for the constructor.



unpermute(self, permute_list)
Unpermute the bit vector according to the

permutation list supplied as the second argument.

If you first permute a bit vector by using permute()

and then unpermute() it using the same permutation

list, you will get back the original bit vector.



write_bits_to_fileobject(self, fp)
This function is meant to write a bit vector directly to

a file like object.  Note that whereas 'write_to_file'

method creates a memory footprint that corresponds exactly

to the bit vector, the 'write_bits_to_fileobject' actually

writes out the 1's and 0's as individual items to the

file object.  That makes this method convenient for

creating a string representation of a bit vector,

especially if you use the StringIO class, as shown in

the test code.



write_to_file(self, file_out)
(Contributed by Joe Davidson) Write the bitvector

to the file object file_out.  (A file object is

returned by a call to open()). Since all file I/O

is byte oriented, the bitvector must be multiple

of 8 bits. Each byte treated as MSB first (0th index).




Data descriptors defined here:


__dict__


dictionary for instance variables (if defined)




__weakref__


list of weak references to the object (if defined)




 





 

class BitVectorIterator

    

    
Methods defined here:


__init__(self, bitvec)



__iter__(self)



next(self)








 

Data

    

       
__author__ = 'Avinash Kak (kak@purdue.edu)'

__copyright__ = '(C) 2010 Avinash Kak. Python Software Foundation.'

__date__ = '2010-April-25'

__url__ = 'http://RVL4.ecn.purdue.edu/~kak/dist/BitVector-2.0.html'

__version__ = '2.0'





 

Author

    

       
Avinash Kak (kak@purdue.edu)