How do I represent and work with n-bit vectors in Python?

Question

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.

@S.Lott: yes, this is in relation to that, but this part has very little to do with that. as you see, I could have done this in C, but I would like to know how to do it in Python, using the built-ins of the language. That is a general question of relevance to others. — oligofren, Jan 27 '10 at 16:26
@oligofren: In that case, suggestions of external libraries would seem to be just as useful to you, assuming they are free -- you can look at the source and see how they've done it (using the built-ins of the language) for your academic interest. — ezod, Jan 27 '10 at 16:53

score 45 · Answer 1 · answered Apr 17 '17 at 20:15

45

I'm surprised that no one has mentioned ints (or I guess long in Python 2). ints 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.

answered Apr 17 '17 at 20:15

jpkotta

9,237
3
29
34

1

Takes seconds per operation on an i7 when you have tens of billions of bits. – Eponymous Jan 23 '18 at 23:26
1

This works great for smallish vectors, like 128 bit. Very simple and built-in. – All The Rage Mar 24 '18 at 17:57
I have a bitvector with two million bits and it seems very slow https://stackoverflow.com/questions/52440611/is-python-bitwise-shift-really-slow – M3RS Sep 21 '18 at 09:34

score 11 · Accepted Answer · edited Sep 10 '20 at 07:29

11

The library BitVector is a pure-Python library for this purpose, and should suit the needs you specified.

edited Sep 10 '20 at 07:29

Boris Verkhovskiy

14,854
11
100
103

answered Jan 27 '10 at 15:01

Håvard S

23,244
8
61
72

3

Good library. Didn't use it, but learned a lot from reading the code. Turns out that in the nitty-gritty details the author of BitVector is using an array of (8 bit) bytes, just like I was pondering. – oligofren Feb 09 '10 at 14:26

score 9 · Answer 3 · answered Jan 27 '10 at 15:00

9

It has lists, which you can populate with bools:

[False] * 20

answered Jan 27 '10 at 15:00

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

1

Would this occupy 20 bytes or 20 bits of memory? I need to use *lots* of these – oligofren Jan 27 '10 at 15:03
5

It would occupy 20+1 pointers. True and False are singletons. – Ignacio Vazquez-Abrams Jan 27 '10 at 15:05
Thanks for the input! I guess I will have to go with the structs module in that case. – oligofren Jan 27 '10 at 15:19

score 9 · Answer 4 · answered Jan 27 '10 at 15:02

9

The bitarray module does this efficiently with booleans.

answered Jan 27 '10 at 15:02

ezod

7,261
2
24
34

score 3 · Answer 5 · answered Jan 27 '10 at 15:00

3

Use struct module.

answered Jan 27 '10 at 15:00

gruszczy

40,948
31
128
181

1

Could you give me an example of creating a 3 byte array and setting a bit? I do not know the basic binary operators in Python. – oligofren Jan 27 '10 at 15:27
I used it only once, when I needed to write some low level stuff. The docs are very fine, though. – gruszczy Jan 27 '10 at 15:53
1

@oligofren see http://www.doughellmann.com/PyMOTW/struct/index.html for a walkthrough. btw the site makes a very fine alternative for getting used to the stdlib. – n611x007 Jan 11 '13 at 19:24

lonetwin · Answer 6 · 2016-11-01T17:44:59.063

A bit dated but I'm going to leave another stdlib option here just for comparison sake. It is also easy to do this using the ctypes module.

For example:

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.

class Simple(ctypes.LittleEndianStructure):
    _pack_ = 1
    _fields_ = [
                 ('one', ctypes.c_ubyte, 8),
                 ('two', ctypes.c_ubyte, 8),
                 ('three', ctypes.c_ubyte, 8)
               ]

s = Simple(0, 2, 256)
bytearray(s)        # bytearray(b'\x00\x02\x00')
s = Simple(0, 2, 255)
bytearray(s)        # bytearray(b'\x00\x02\xff')

class Simple(ctypes.BigEndianStructure):
    _pack_ = 1
    _fields_ = [
                 ('one', ctypes.c_ubyte, 8),
                 ('two', ctypes.c_ubyte, 8),
                 ('three', ctypes.c_ubyte, 8)
               ]

s = Simple(0, 2, 256)
bytearray(s)        # bytearray(b'\x00\x02\x00')
s = Simple(0, 2, 255)
bytearray(s)        # bytearray(b'\x00\x02\xff')

s.two |= 3
bytearray(s)        # bytearray(b'\x00\x03\xff')

or something more straight forward like this:

class bit_vector(Structure):
    _fields_ = [('bits', c_uint32, 24),
                ('unused', c_uint32, 8),
                ]

bv = bit_vector()
# turn on the 18th bit -- being explicit just to demo it
bv.bits |= int('000000000000000001000000', 2)
bin(bv.bits)   # 0b1000000

score 1 · Answer 7 · answered Oct 12 '12 at 12:20

1

There is also the pure-Python python-bitstring (with Python 3 support).

answered Oct 12 '12 at 12:20

Janus Troelsen

20,267
14
135
196

How do I represent and work with n-bit vectors in Python?

7 Answers7

Linked

Related