In an assignment I am currently working on we need to work with bit vectors, but I am very unsure of how to do this in Python. They should be able to be from 4 bits to 20 bits. I have never worked with bit vector before, but I guess that one would one create arrays of unsigned bytes that you manipulated using the usual AND/OR/XOR operations.
The important restriction here is: I cannot rely on any libraries other than those supplied with standard Python.
I think I know how I would do this in C using arrays of 8 bit unsigned bytes: e.g. to turn the 18th bit of a zeroed array into a one, I would do something like my_bit_array[3] &= 1<<2
But since Python is dynamically typed and does not have a built-in array type, how would I go about doing this in a pythonic way?
And is it possible (how?) to express a bit vector of size 20? I am thinking of perhaps making a 24 bit / 3 byte vector and ignoring the 4 bits.
I'm surprised that no one has mentioned int
s (or I guess long
in Python 2). int
s can be arbitrarily large, you can use bitwise operators on them, they're fast, and the code looks like bit twiddling code in C (I consider that to be an advantage).
x = 0 # empty
x |= 1<<19 # set bit 19
x &= ~(1<<19) # clear bit 19
x ^= 1<<19 # toggle bit 19
x = ~x # invert *all* bits, all the way to infinity
mask = ((1<<20)-1) # define a 20 bit wide mask
x &= mask # ensure bits 20 and higher are 0
x ^= mask # invert only bits 0 through 19
(x >> 19) & 1 # test bit 19
(x >> 16) & 0xf # get bits 16 through 20.
I've used this for bitvectors hundreds of bits long.