如何在Python中表示和处理n位向量？

Question

我目前正在处理一个任务，需要使用位向量（bit vectors），但是我非常不确定如何在Python中实现。它们应该可以从4位到20位。我以前没有使用过位向量，但我猜想你可以创建由无符号字节组成的数组，并使用常规的AND/OR/XOR操作进行操作。

这里的重要限制是：除了标准Python提供的库之外，我不能依赖于任何其他库。

我认为我知道如何在C中使用8位无符号字节数组来完成这项任务，例如，将零化数组的第18位变为1，我会做类似这样的事情： my_bit_array [3]＆= 1 << 2

但是，由于Python是动态类型的，并且没有内置的数组类型，我该如何用Pythonic的方式解决这个问题呢？

而且，是否有可能（如何）表示大小为20的位向量？我考虑可能制作一个24位/3字节向量并忽略4位。

- oligofren

---

依赖外部库存在什么问题？ - ezod

@ezod：可能是因为这是一份作业。 - S.Lott

@S.Lott：是的，这与那个有关，但这部分与那个几乎没有什么关系。正如您所看到的，我本可以用C语言来完成这个任务，但我想知道如何使用Python语言的内置函数来实现它。这是一个对其他人有普遍意义的一般性问题。 - oligofren

@oligofren: 如果是这种情况，外部库的建议对您来说也同样有用，假设它们是免费的 -- 您可以查看源代码并了解它们是如何使用语言内置功能实现的，以满足您的学术兴趣。 - ezod

Answer 1

我很惊讶没有人提到 int（或者在 Python 2 中是 long）。int 可以是任意大的，你可以对它们使用位运算符，它们很快，代码看起来像 C 语言中的位操作代码（我认为这是一个优点）。

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.

我已经将这个用于数百位长的位向量。

- jpkotta

---

当您拥有数十亿位时，在i7上每个操作只需要几秒钟。 - Eponymous

这对于小型向量非常有效，例如128位。非常简单和内置。 - All The Rage

我有一个包含两百万位的位向量，但似乎非常缓慢。 - M3RS

Answer 2

位向量库BitVector是一个纯Python库，可满足您所需的要求。

- Håvard S

---

好的图书馆。我没有使用它，但从阅读代码中学到了很多。结果发现，在细节方面，BitVector的作者使用了一个（8位）字节数组，就像我一直在考虑的那样。 - oligofren

Answer 3

它有列表，您可以使用布尔值填充：

[False] * 20

- Ignacio Vazquez-Abrams

---

这会占用20字节还是20位内存？我需要使用很多这些。 - oligofren

它将占用20+1个指针。True和False是单例。 - Ignacio Vazquez-Abrams

谢谢您的建议！我想在这种情况下我将选择使用structs模块。 - oligofren

Answer 4

bitarray 模块使用布尔值高效地实现了这一点。

- ezod

Answer 5

有点过时，但出于比较的目的，我会在此提供另一个stdlib选项。使用ctypes模块也很容易实现这一点。

例如：

是否有可能（如何？）表示大小为20的位向量？ 我考虑使用24位/ 3字节向量并忽略4个位。

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')

或者更直接的说法是这样的：

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

- lonetwin

Answer 6

使用 struct 模块。

- gruszczy

---

你能给我一个创建三字节数组并设置位的例子吗？我不知道Python中基本的二进制运算符。 - oligofren

我只用过一次，当我需要写一些低级别的东西时。文档非常好，虽然。 - gruszczy

@oligofren 可以查看 http://www.doughellmann.com/PyMOTW/struct/index.html 进行详细了解。顺便说一下，该网站是熟悉标准库的很好选择。 - n611x007

Answer 7

还有纯Python的python-bitstring（支持Python 3）。

- Janus Troelsen