Python 中高效的位数组运算

Question

我正在实现一个类，用于在 Python 中处理位值数组。到目前为止，这就是我所做的：

class Bitarray:
    """ Representation of an array of bits.
    :param bits: the list of boolean values (i.e. {False, True}) of the bitarray.
    """
    def __init__(self, values:list[bool]):
        self._bits:list[bool] = values
        self._length:int = len(values)

    @staticmethod
    def from_bytes(data:bytes, byteorder:str = None):
        def _access_bit(data, index):
            """ Credits: https://stackoverflow.com/a/43787831/23022499
            """
            base = int(index // 8)
            shift = int(index % 8)
            return (data[base] >> shift) & 0x1
        
        if byteorder == None:
            byteorder = sys.byteorder
        elif byteorder != 'little' and byteorder != 'big':
            raise ValueError('Param byteorder must be either "little" or "big".')
        
        bin_data = [_access_bit(data, i) for i in range(len(data) * 8)]
        bin_data = [bool(b) for b in bin_data]
        return Bitarray(bin_data) if byteorder == 'big' else Bitarray(bin_data[::-1])
    
    def __getitem__(self, index) -> bool:
        return self._bits[index]
    
    def __len__(self) -> int:
        return self._length
    
    # bit-wise operations
    def __and__(self, other):
        if type(other) != Bitarray:
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self), type(other)))
        
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        
        return Bitarray([(a & b) for a, b in zip(self._bits, other._bits)])

    def __or__(self, other):
        if type(other) != Bitarray:
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self), type(other)))
        
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        
        return Bitarray([(a | b) for a, b in zip(self._bits, other._bits)])

    def __xor__(self, other):
        if type(other) != Bitarray:
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self).__name__, type(other).__name__))
        
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        
        return Bitarray([(a ^ b) for a, b in zip(self._bits, other._bits)])

    # to string
    def __str__(self):
        return ''.join(str(int(b)) for b in self._bits)

如果您想知道用法，我想使用

os.urandom()

生成随机值，然后对这些值执行按位运算。一个例子：

import os
import sys

a = Bitarray.from_bytes(os.urandom(16 // 8), sys.byteorder)
b = Bitarray.from_bytes(os.urandom(16 // 8), sys.byteorder)

print('XOR result: {}'.format(a ^ b))

到目前为止，我所做的一切都是有效的。但我很确定这效率太低了，对于那些正在阅读本文并且对 Python 有更多了解的人来说，我刚刚犯了一些可怕的罪过。 ：P 抛开笑话不谈，迭代布尔值进行按位运算可不太好，对吧？有没有更有效的方法来做到这一点？

附注对于那些好奇的人，我正在尝试构建一个使用随机密钥和异或操作的加密协议。我了解一些模块，如密码学、位数组等，但我认为尝试自己实现一些东西会更有趣。抱歉缺少文档和评论，我会尽力改进！

编辑：当然，有人可能会问，如果我可以使用字节执行按位运算，为什么我需要使用位数组。我需要访问单个位值，并且希望我的 Bitarray 类能够执行按位操作，而不必每次都移回字节。

Answer 1

我建议使用Python的无限精度整数来保存值，因为所有的二进制运算都可以直接在它们上执行：

import os
import sys

class Bitarray:
    """ Representation of an array of bits.
    :param bits: the list of boolean values (i.e. {False, True}) of the bitarray.
    """
    def __init__(self, bits, value=0):
        if value >= (1 << bits):
            raise ValueError(f'value does not fit into {bits} bit(s)')
        self._bits: int = value
        self._length: int = bits

    @classmethod
    def from_bytes(cls, data: bytes, byteorder: str = None):
        if byteorder is None:
            byteorder = sys.byteorder
        elif byteorder != 'little' and byteorder != 'big':
            raise ValueError('Param byteorder must be either "little" or "big".')
        value = int.from_bytes(data, byteorder)
        return cls(len(data) * 8, value)

    def __getitem__(self, index) -> bool:
        return bool(self._bits & (1 << index))

    def __len__(self) -> int:
        return self._length

    # bit-wise operations
    def __and__(self, other):
        if not isinstance(other, Bitarray):
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self), type(other)))
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        return Bitarray(self._length, self._bits & other._bits)

    def __or__(self, other):
        if not isinstance(other, Bitarray):
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self), type(other)))
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        return Bitarray(self._length, self._bits | other._bits)

    def __xor__(self, other):
        if not isinstance(other, Bitarray):
            raise TypeError("Unsupported operand type(s) for &: '{}' and '{}'".format(type(self).__name__, type(other).__name__))
        if self._length != len(other):
            raise IndexError("The arguments for bitwise operations must have same length.")
        return Bitarray(self._length, self._bits ^ other._bits)

    # to string
    def __str__(self):
        return format(self._bits, f'0{self._length}b')

    def __repr__(self):
        length = (self._length + 3) // 4
        return f'Bitarray(bits={self._length}, value=0x{self._bits:0{length}X})'

a = Bitarray(8, 0xAF)
b = Bitarray(8, 0x55)
print(repr(a), repr(b))
print(a & b)
print(a | b)
print(a ^ b)
c = Bitarray.from_bytes(os.urandom(32))
print(repr(c))
d = Bitarray.from_bytes(b'\xff\x00')
print(repr(d))
e = Bitarray.from_bytes(b'\xff\x00', 'big')
print(repr(e))

输出：

Bitarray(bits=8, value=0xAF) Bitarray(bits=8, value=0x55)
00000101
11111111
11111010
Bitarray(bits=256, value=0x976E921A9C93C7D5D9C4BB6722B38064A04EA882CA4DF76981F52C7097E0DDFF)
Bitarray(bits=16, value=0x00FF)
Bitarray(bits=16, value=0xFF00)