BitVector.py
Author: Avinash Kak (kak@purdue.edu)
Version: 1.0
Download Version 1.0
Switch to Version 1.1
Switch to Version 1.2
Switch to Version 1.3
Switch to Version 1.3.1
Switch to Version 1.3.2 (important for Windows users)
INTRODUCTION
The BitVector class is 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 bit packing is based on an internet posting by Josiah Carlson who was responding to a query by Nitin Madnani on a mailing list devoted to Pyrex.
The following methods/operators are supported by the BitVector class:
CONSTRUCTING BIT VECTORS
There are three ways to construct a bit vector with the class shown here:
bv = BitVector( N )
which creates a bit vector that can hold N bits; or
bv = BitVector( [1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1] )
which creates a bit vector that is initialized with the bits shown in the argument. If it is desired to read a disk file into bit vectors, the best way to do that is to first construct an instance of BitVector by
bv = BitVector( filename )
This bit vector itself is incapable of holding the bits. To now create a bit vector that actually holds 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 and, with this example call,
it will pack 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()
DISPLAYING BIT VECTORS
A bit vector
bv can be displayed on a terminal by
bv.show_bitvec()
ACCESSING INDIVIDUAL BITS
Any single bit of the bit vector
bv can be set to 1 or 0 by
bv.setbit( M, 1_or_0 )
or more conveniently by
bv[M] = 1_or_0
print bv[M]
for setting the bit at the position that is indexed M. You can also retrieve the bit at position
M by
bv.getbit( M )
although obviously the syntax bv[M] would be more convenient.
LOGICAL OPERATIONS ON BIT VECTORS
Given two bit vectors bv1 and bv2, you can perform bitwise logical operations on them by
result_bv = bv1 | bv2
result_bv = bv1 & bv2
result_bv = bv1 ^ bv2
result_bv = ~ bv1
OTHER OPERATIONS ON BIT VECTORS
Additional operations supported on bit vectors are
bv_permuted = bv.permute( permutation_list )
bv_unpermuted = bv.unpermute( permutation_list )
The
unpermute() method undoes the permutation carried out by
the permute() method. For a given bit vector, an application
of permute() following by an application of unpermute(),
both invoked with the same permutation list, will restore the original bit vector.
The BitVector class also supports the following circular shift
operations:
bitvec << N
bitvec >> N
for a circular rotation by N bit positions to the left and to the right.
A bit vector containing an even number of bits can be divided into two
equal halves by
[left_bitbvec, right_bitvec] = bitvec.divide_into_two()
where
left_bitvec and right_bitvec hold references
to the two returned bit vectors. (This is useful in block encryption
studies where you want to divide the input bit blocks into two halves and
operate on them separately before joining them up again.) Two bitvectors
can be concatenated by
new_bitvic = bitvec1 + bitvec2
The bit vector returned by '+' will be a concatenation of
bitvec1 and bitvec2.
THE STORAGE OF BIT VECTORS
The bits of a bit array are stored in 16-bit unsigned shorts. The very first thing that the constructor does is to figure out in line (A18) 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 (A16) would be set to 4. Line (A19) then creates an array of 2-byte ints and initializes it with the required number of zeros. Lines (A20) and (A22) then shift the bits into the array of two-byte ints. Line (A21) is used if the constructor is called with just the number of bits in a bit vector. On the other hand, line (A23) is used when the actual bits are supplied to the constructor in the form of a list of bits.
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.
Note also that the very first thing the constructor tries to figure out in lines (A3) through (A17) is whether you are calling the constructor with an integer as its argument, in which case the integer is interpreted as the size of the bit vector, or with a list of bits, in which case the bit vector is initialized with the bits in the list, or with a string, in which case the string is interpreted as the name of the disk file from which to read the bits.
Lines (A4), (A5) and (A6) are for the following sort of a call
bv = BitVector( 7 )
This will construct a bit vector for holding 7 bits. On the other hand, lines (A7) through (A10) are for the case when the constructor is called with the following sort of a call:
bv = BitVector( [1, 0, 1, 1, 0, 0, 1] )
Now the bit vector constructed will be initialized at the same time with the supplied bits. Finally, the lines (A11) through (A15) are for the following sort of a call
bv = BitVector( filename )
This returns a bit vector on which you can invoke the function read_bits_from_file(). This function then returns a bit vector with the bits from the file.
ACKNOWLEDGEMENTS
Oleg Broytmann has sent me a list of improvements for the BitVector class. These will be implemented as time permits. The version posted already includes a couple of improvements suggested by Oleg, such as the aliasing for __getitem__, __setitem__, etc. and the overloading of the operators.
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 & Sons, New York, 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. For further information, visit www.programming-with-objects.com.
import sys
import array
import exceptions
import operator
_hexdict = { '0' : '0000', '1' : '0001', '2' : '0010', '3' : '0011',
'4' : '0100', '5' : '0101', '6' : '0110', '7' : '0111',
'8' : '1000', '9' : '1001', 'a' : '1010', 'b' : '1011',
'c' : '1100', 'd' : '1101', 'e' : '1110', 'f' : '1111' }
def _readblock( blocksize, FILEIN ): #(R1)
global hexdict #(R2)
bitstring = '' #(R3)
i = 0 #(R4)
while ( i < blocksize / 8 ): #(R5)
i += 1 #(R6)
byte = FILEIN.read(1) #(R7)
if byte == '': #(R8)
return bitstring #(R9)
hexvalue = hex( ord( byte ) ) #(R10)
hexvalue = hexvalue[2:] #(R11)
if len( hexvalue ) == 1: #(R12)
hexvalue = '0' + hexvalue #(R13)
bitstring += _hexdict[ hexvalue[0] ] #(R14)
bitstring += _hexdict[ hexvalue[1] ] #(R15)
return bitstring #(R16)
class BitVector( object ): #(A1)
def __init__( self, list_or_len_or_str ): #(A2)
if isinstance( list_or_len_or_str, (int, long) ): #(A3)
self.filename = None #(A4)
self.size = list_or_len_or_str #(A5)
bits = [0] * list_or_len_or_str #(A6)
elif isinstance( list_or_len_or_str, (list, tuple) ): #(A7)
self.filename = None #(A8)
self.size = len( list_or_len_or_str ) #(A9)
bits = list_or_len_or_str #(A10)
elif isinstance( list_or_len_or_str, (str) ): #(A11)
self.filename = list_or_len_or_str #(A12)
self.FILEIN = open( list_or_len_or_str, 'rb' ) #(A13)
self.size = 0 #(A14)
self.more_to_read = True
return #(A15)
else: #(A16)
raise exceptions.TypeError,"wrong arg for constructor" #(A17)
two_byte_ints_needed = (len(bits) + 15) // 16 #(A18)
self.vector = array.array( 'H', [0]*two_byte_ints_needed ) #(A19)
if isinstance( list_or_len_or_str, (int, long) ): #(A20)
map( self.setbit, enumerate(bits), bits) #(A21)
else: #(A22)
map( self.setbit, enumerate(bits), list_or_len_or_str ) #(A23)
# Set the bit at the designated position to the value shown:
def setbit( self, posn, val ): #(B1)
if val not in (0, 1): #(B2)
raise exceptions.ValueError, "incorrect value for a bit" #(B3)
if isinstance( posn, (tuple) ): #(B4)
posn = posn[0] #(B5)
if posn >= self.size: #(B6)
raise exceptions.ValueError, "index range error" #(B7)
block_index = posn // 16 #(B8)
shift = posn & 15 #(B9)
cv = self.vector[block_index] #(B10)
if ( cv >> shift ) & 1 != val: #(B11)
self.vector[block_index] = cv ^ (1 << shift) #(B12)
# Get the bit from the designated position:
def getbit( self, posn ): #(C1)
if posn >= self.size: #(C2)
raise exceptions.ValueError, "index range error" #(C3)
return ( self.vector[posn//16] >> (posn&15) ) & 1 #(C4)
# Display the bit vector as a bit string:
def show_bitvec( self ): #(D1)
i = 0 #(D2)
while ( i < self.size ): #(D3)
sys.stdout.write( str(self.getbit( i )) ) #(D4)
i += 1 #(D5)
print #(D6)
# 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:
def __xor__(self, other): #(E1)
if self.size != other.size: #(E2)
raise exceptions.AttributeError,"bitvecs unequal in size"#(E3)
res = BitVector(self.size) #(E4)
res.vector = map(operator.__xor__, self.vector, other.vector)#(E5)
return res #(E6)
# 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:
def __and__(self, other): #(F1)
if self.size != other.size: #(F2)
raise exceptions.AttributeError,"bitvecs unequal in size"#(F3)
res = BitVector(self.size) #(F4)
res.vector = map(operator.__and__, self.vector, other.vector)#(F5)
return res #(F6)
# 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:
def __or__(self, other): #(G1)
if self.size != other.size: #(G2)
raise exceptions.AttributeError,"bitvecs unequal in size"#(G3)
res = BitVector(self.size) #(G4)
res.vector = map( operator.__or__, self.vector, other.vector)#(G5)
return res #(G6)
# Invert the bits in the bit vector on which the method is
# invoked and return the result as a new bit vector:
def __invert__(self): #(H1)
res = BitVector(self.size) #(H2)
res.vector = map( operator.__inv__, self.vector ) #(H3)
return res #(H4)
# 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:
def __add__(self, other): #(J1)
i = 0 #(J2)
outlist = [] #(J3)
while ( i < self.size ): #(J4)
outlist.append( self.getbit(i) ) #(J5)
i += 1 #(J6)
i = 0 #(J7)
while ( i < other.size ): #(J8)
outlist.append( other.getbit(i) ) #(J9)
i += 1 #(J10)
return BitVector( outlist ) #(J11)
# Return the number of bits in a bit vector:
def getsize(self): #(K1)
return self.size #(K2)
# When reading in a loop from a file that contains an
# exact multiple of blocksize/8 bytes, the flag
# self.more_to_read will be set to false only in the
# next iteration of the loop after the last blocksize
# bits have been. Therefore, the user of this function
# must check that this function has actually returned
# a non-zero number of bytes. This can be done by
# making sure that bitvec.getsize() is greater than zero
# for each bit vector constructed from the bitstring
# returned by this function.
def read_bits_from_file(self, blocksize): #(L1)
error_str = '''You need to first construct a BitVector
object with a filename as argument''' #(L2)
if self.filename == None: #(L3)
raise exceptions.SyntaxError, error_str #(L4)
bitstring = _readblock( blocksize, self.FILEIN ) #(L5)
if len(bitstring) < blocksize:
self.more_to_read = False
bitlist = map( lambda x: int(x), list( bitstring ) ) #(L6)
return BitVector( bitlist ) #(L7)
# Divides an even-sized bit vector into two and returns
# the two halves as a list of two bit vectors.
def divide_into_two(self): #(M1)
if self.size % 2 != 0: #(M2)
raise exceptions.ValueError, "must have even num bits" #(M3)
i = 0 #(M4)
outlist1 = [] #(M5)
while ( i < self.size /2 ): #(M6)
outlist1.append( self.getbit(i) ) #(M7)
i += 1 #(M8)
outlist2 = [] #(M9)
while ( i < self.size ): #(M10)
outlist2.append( self.getbit(i) ) #(M11)
i += 1 #(M12)
return [ BitVector( outlist1 ), BitVector( outlist2 ) ] #(M13)
# Permute a bit vector according to the indices shown in the
# second argument list. Return the permuted bit vector as a
# new bit vector.
def permute(self, permute_list): #(N1)
if max(permute_list) > self.size -1: #(N2)
raise exceptions.ValueError, "Bad permutation index" #(N3)
outlist = [] #(N4)
i = 0 #(N5)
while ( i < len( permute_list ) ): #(N6)
outlist.append( self.getbit( permute_list[i] ) ) #(N7)
i += 1 #(N8)
return BitVector( outlist ) #(N9)
# 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.
def unpermute(self, permute_list): #(P1)
if max(permute_list) > self.size -1: #(P2)
raise exceptions.ValueError, "Bad permutation index" #(P3)
if self.size != len( permute_list ): #(P4)
raise exceptions.ValueError,"Bad size for permute list" #(P5)
out_bv = BitVector( self.size ) #(P6)
i = 0 #(P7)
while ( i < len(permute_list) ): #(P8)
out_bv.setbit( permute_list[i], self.getbit(i) ) #(P9)
i += 1 #(P10)
return out_bv #(P11)
# Contributed by Joe Davidson
# Write the bitvector to the file object file_out.
# (A file object is returned by a call to open()).
# Hopefully the bitvector is a multiple of 8 bits ...
# Each byte treated as MSB first (0th index)
def write_to_file(self, file_out): #(Q1)
for byte in range(self.size/8 ): #(Q2)
value = 0 #(Q3)
for bit in range(8): #(Q4)
value += (self.getbit( byte*8 + (7 - bit) ) << bit ) #(Q5)
file_out.write( chr(value) ) #(Q6)
# For closing a file object that was used for reading
# the bits into one or more BitVector objects
def close_file_object(self): #(S1)
if self.filename == None: #(S2)
raise exceptions.SyntaxError, "No associated open file" #(S3)
self.FILEIN.close() #(S4)
# For an in-place left circular shift by n bit positions:
def __lshift__( self, n ): #(T1)
for i in range(n): #(T2)
self.circular_rotate_left_by_one() #(T3)
# For an in-place right circular shift by n bit positions:
def __rshift__( self, n ): #(U1)
for i in range(n): #(U2)
self.circular_rotate_right_by_one() #(U3)
# For a one-bit in-place left circular shift:
def circular_rotate_left_by_one(self): #(V1)
size = len(self.vector) #(V2)
bitstring_leftmost_bit = self.vector[0] & 1 #(V3)
left_most_bits = map(operator.__and__, self.vector, [1]*size)#(V4)
left_most_bits.append(left_most_bits[0]) #(V5)
del(left_most_bits[0]) #(V6)
self.vector = map(operator.__rshift__, self.vector, [1]*size)#(V7)
self.vector = map( operator.__or__, self.vector, \
map(operator.__lshift__, left_most_bits, [15]*size) ) #(V8)
self.setbit(self.size -1, bitstring_leftmost_bit) #(V9)
# For a one-bit in-place right circular shift:
def circular_rotate_right_by_one(self): #(W1)
size = len(self.vector) #(W2)
bitstring_rightmost_bit = self.getbit(self.size -1) #(W3)
right_most_bits = map( operator.__and__,
self.vector, [0x8000]*size ) #(W4)
map( operator.__and__, self.vector, [~0x8000]*size ) #(W5)
right_most_bits.insert(0, bitstring_rightmost_bit) #(W6)
right_most_bits.pop() #(W7)
self.vector = map(operator.__lshift__, self.vector, [1]*size)#(W8)
self.vector = map( operator.__or__, self.vector, \
map(operator.__rshift__, right_most_bits, [15]*size) ) #(W9)
self.setbit(0, bitstring_rightmost_bit) #(W10)
# 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.
def circular_rot_left(self): #(X1)
max_index = (self.size -1) // 16 #(X2)
left_most_bit = self.vector[0] & 1 #(X3)
self.vector[0] = self.vector[0] >> 1 #(X4)
for i in range(1, max_index + 1): #(X5)
left_bit = self.vector[i] & 1 #(X6)
self.vector[i] = self.vector[i] >> 1 #(X7)
self.vector[i-1] |= left_bit << 15 #(X8)
self.setbit(self.size -1, left_most_bit) #(X9)
# 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.
def circular_rot_right(self): #(Y1)
max_index = (self.size -1) // 16 #(Y2)
right_most_bit = self.getbit(self.size -1) #(Y3)
self.vector[max_index] &= ~0x8000 #(Y4)
self.vector[max_index] = self.vector[max_index] << 1 #(Y5)
for i in range(max_index-1, -1, -1): #(Y6)
right_bit = self.vector[i] & 0x8000 #(Y7)
self.vector[i] &= ~0x8000 #(Y8)
self.vector[i] = self.vector[i] << 1 #(Y9)
self.vector[i+1] |= right_bit >> 15 #(Y10)
self.setbit(0, right_most_bit) #(Y11)
# Allow array like subscripting for getting and setting:
__getitem__ = getbit #(Z1)
__setitem__ = setbit #(Z2)
# Allow len() to work:
__len__ = getsize #(Z3)
#------------------------ End of Class Definition -----------------------
#------------------------ Test Code Follows -----------------------
if __name__ == '__main__':
bv1 = BitVector( [1, 0, 0, 1] )
bv1.show_bitvec() # 1001
bv2 = BitVector( [1, 1, 0, 1] )
bv2.show_bitvec() # 1101
# Show array like access for getting and setting:
print bv2[2] # 0
bv2[2] = 1
bv2.show_bitvec() # 1111
bv2[2] = 0
# Experiments with bit-wise logical operations:
bv3 = bv1 | bv2
bv3.show_bitvec() # 1101
bv3 = bv1 & bv2
bv3.show_bitvec() # 1001
bv3 = bv1 + bv2
bv3.show_bitvec() # 10011101
bv4 = BitVector( 3 )
bv4.show_bitvec() # 000
bv5 = bv3 + bv4
bv5.show_bitvec() # 10011101000
bv6 = ~bv5
bv6.show_bitvec() # 01100010111
bv7 = bv5 & bv6
bv7.show_bitvec() # 00000000000
bv7 = bv5 | bv6
bv7.show_bitvec() # 11111111111
# Try setbit and getsize:
bv7.setbit( 7, 0 )
bv7.show_bitvec() # 11111110111
print bv7.getsize() # 11
bv8 = (bv5 & bv6) ^ bv7
bv8.show_bitvec() # 11111110111
# Construct a bit vector from a list of bits:
bv = BitVector( [0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1] )
bv.show_bitvec() # 0010010100101001
# Construct a bit vector from a file:
bv = BitVector( 'junk.txt' )
bv.show_bitvec() # nothing to show
bv1 = bv.read_bits_from_file(64)
bv1.show_bitvec()
bv2 = bv.read_bits_from_file(64)
bv2.show_bitvec()
bv3 = bv1 ^ (bv2)
bv3.show_bitvec()
[bv4, bv5] = bv3.divide_into_two()
bv4.show_bitvec()
bv5.show_bitvec()
# Permute a bit vector:
bv1 = BitVector( [1, 0, 0, 1, 1, 0, 1] )
bv1.show_bitvec() # 1001101
bv2 = bv1.permute( [6, 2, 0, 1] )
bv2.show_bitvec() # 1010
bv3 = BitVector( [1, 1, 0, 0, 0, 1, 1] )
bv3.show_bitvec() # 1100011
bv4 = bv1 & bv3
bv4.show_bitvec() # 1000001
print
# Read a file from the beginning to end:
bv = BitVector( 'junk3.txt' )
while (bv.more_to_read):
bv_read = bv.read_bits_from_file( 64 )
if bv_read.getsize() > 0:
bv_read.show_bitvec()
print
# Experiment with closing a file object and start
# extracting bit vectors from the file from
# the beginning again:
bv.close_file_object()
bv = BitVector( 'junk3.txt' )
bv1 = bv.read_bits_from_file(64)
bv1.show_bitvec()
FILEOUT = open( 'junk4.txt', 'w' )
bv1.write_to_file( FILEOUT )
FILEOUT.close
# Experiment in 64-bit permutation and unpermutation:
# The permutation array was generated separately by the
# Fisher-Yates shuffle algorithm:
bv2 = bv1.permute( [22, 47, 33, 36, 18, 6, 32, 29, 54, 62, 4,
9, 42, 39, 45, 59, 8, 50, 35, 20, 25, 49,
15, 61, 55, 60, 0, 14, 38, 40, 23, 17, 41,
10, 57, 12, 30, 3, 52, 11, 26, 43, 21, 13,
58, 37, 48, 28, 1, 63, 2, 31, 53, 56, 44, 24,
51, 19, 7, 5, 34, 27, 16, 46] )
bv2.show_bitvec()
bv3 = bv2.unpermute( [22, 47, 33, 36, 18, 6, 32, 29, 54, 62, 4,
9, 42, 39, 45, 59, 8, 50, 35, 20, 25, 49,
15, 61, 55, 60, 0, 14, 38, 40, 23, 17, 41,
10, 57, 12, 30, 3, 52, 11, 26, 43, 21, 13,
58, 37, 48, 28, 1, 63, 2, 31, 53, 56, 44, 24,
51, 19, 7, 5, 34, 27, 16, 46] )
bv3.show_bitvec()
print
print
# Try circular shifts to the left and to the right
bv3.show_bitvec()
bv3 << 7
bv3.show_bitvec()
bv3 >> 7
bv3.show_bitvec()
print len( bv3 ) # 64