如何在 Python 中表示和使用 n 位向量？

Question

在我目前正在进行的一项作业中，我们需要使用位向量，但我非常不确定如何在 Python 中执行此操作。它们应该可以是 4 位到 20 位。我以前从未使用过位向量，但我想人们会创建使用通常的 AND/OR/XOR 操作进行操作的无符号字节数组。

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

我想我知道如何在 C 中使用 8 位无符号字节数组来做到这一点： 例如，要将归零数组的第 18 位变为 1，我会执行类似的操作 my_bit_array[3] &= 1<<2

但是由于 Python 是动态类型的并且没有内置数组类型，我将如何以 pythonic 方式执行此操作？

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

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.

我已将其用于数百位长的位向量。

Answer 2

库 BitVector 是用于此目的的纯 Python 库，并且应该满足您指定的需求。

Answer 3

bitarray 模块可以使用布尔值有效地完成此操作。

Answer 4

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

[False] * 20

Answer 5

使用 struct 模块。

Answer 6

有点过时，但我将在这里留下另一个 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

Answer 7

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