Как мне представить и работать с n-битными векторами в Python?

Question

В задании, над которым я сейчас работаю, нам нужно работать с битовыми векторами, но я очень не уверен, как это сделать в Python. Они должны быть от 4 до 20 бит. Я никогда раньше не работал с битовым вектором, но думаю, что можно было бы создать массивы беззнаковых байтов, которыми вы манипулировали, используя обычные операции AND / OR / XOR.

Важное ограничение заключается в следующем: я не могу полагаться на любые библиотеки, кроме тех, которые поставляются со стандартным Python.

Думаю, я знаю, как бы я делал это в C, используя массивы 8-битных неподписанных байтов: например чтобы превратить 18-й бит обнуленного массива в один, я бы сделал что-то вроде my_bit_array [3] & = 1 << 2 </p>

Но так как Python динамически типизирован и не имеет встроенного типа массива, как бы я поступил так с помощью Pythonic?

И возможно ли (как?) Выразить битовый вектор размером 20? Я думаю о том, чтобы сделать 24-битный / 3-байтовый вектор и игнорировать 4-битные.

Answer 1

Я удивлен, что никто не упомянул int s (или я предполагаю long в Python 2). int s могут быть произвольно большими, вы можете использовать для них побитовые операторы, они быстрые, и код выглядит как битовый код в 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

Модуль bitarray делает это эффективно с логическими значениями.

Answer 3

Библиотека BitVector для этой цели - библиотека на чистом Python и должна соответствовать указанным вами потребностям.

Answer 4

У него есть списки, которые вы можете заполнить с помощью bools:

[False] * 20

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

Answer 6

Существует также чистый Python python-bitstring (с поддержкой Python 3).

Answer 7

Использовать struct module.