Python中与Java的BitSet相当的模块

Question

是否有一个 Python 类或模块实现了类似于 BitSet 的结构？

- Mantas Vidutis

---

对于非Java程序员，什么是BitSet？你想实现什么目标？即使没有等同的解决方案，可能存在一种好的、Pythonic的方法来解决您的问题。 - Sean McSomething

基本上，BitSet 是一串带有位运算的比特串。可以对其应用位运算。该集合还可以通过将比特或比特集附加到当前比特集的末尾来扩展。 - Mantas Vidutis

Answer 1

标准库中没有相关内容。请尝试：

http://pypi.python.org/pypi/bitarray

- Glenn Maynard

Answer 2

看看这个Python 3的实现方法。

这个实现方法基本上利用了Python 3内置的int类型，这是Python 3中的任意精度整数类型（其中long是Python2中的等效类型）。

#! /usr/bin/env python3

"""
bitset.py

Written by Geremy Condra

Licensed under GPLv3

Released 3 May 2009

This module provides a simple bitset implementation
for Python.
"""

from collections import Sequence
import math

class Bitset(Sequence):
    """A very simple bitset implementation for Python.

    Note that, like with normal numbers, the leftmost
    index is the MSB, and like normal sequences, that
    is 0.

    Usage:
        >>> b = Bitset(5)
        >>> b
        Bitset(101)
        >>> b[:]
        [True, False, True]
        >>> b[0] = False
        >>> b
        Bitset(001)
        >>> b << 1
        Bitset(010)
        >>> b >> 1
        Bitset(000)
        >>> b & 1
        Bitset(001)
        >>> b | 2
        Bitset(011)
        >>> b ^ 6
        Bitset(111)
        >>> ~b
        Bitset(110)
    """

    value = 0
    length = 0

    @classmethod
    def from_sequence(cls, seq):
        """Iterates over the sequence to produce a new Bitset.

        As in integers, the 0 position represents the LSB.
        """
        n = 0
        for index, value in enumerate(reversed(seq)):
            n += 2**index * bool(int(value))
        b = Bitset(n)
        return b

    def __init__(self, value=0, length=0):
        """Creates a Bitset with the given integer value."""
        self.value = value
        try: self.length = length or math.floor(math.log(value, 2)) + 1
        except Exception: self.length = 0

    def __and__(self, other):
        b = Bitset(self.value & int(other))
        b.length = max((self.length, b.length))
        return b

    def __or__(self, other):
        b = Bitset(self.value | int(other))
        b.length = max((self.length, b.length))
        return b

    def __invert__(self):
        b = Bitset(~self.value)
        b.length = max((self.length, b.length))
        return b

    def __xor__(self, value):
        b = Bitset(self.value ^ int(value))
        b.length = max((self.length, b.length))
        return b

    def __lshift__(self, value):
        b = Bitset(self.value << int(value))
        b.length = max((self.length, b.length))
        return b

    def __rshift__(self, value):
        b = Bitset(self.value >> int(value))
        b.length = max((self.length, b.length))
        return b

    def __eq__(self, other):
        try:
            return self.value == other.value
        except Exception:
            return self.value == other

    def __int__(self):
        return self.value

    def __str__(self):
        s = ""
        for i in self[:]:
            s += "1" if i else "0"
        return s

    def __repr__(self):
        return "Bitset(%s)" % str(self)

    def __getitem__(self, s):
        """Gets the specified position.

        Like normal integers, 0 represents the MSB.
        """
        try:
            start, stop, step = s.indices(len(self))
            results = []
            for position in range(start, stop, step):
                pos = len(self) - position - 1
                results.append(bool(self.value & (1 << pos)))
            return results
        except:
            pos = len(self) - s - 1
            return bool(self.value & (1 << pos))

    def __setitem__(self, s, value):
        """Sets the specified position/s to value.

        Like normal integers, 0 represents the MSB.
        """
        try:
            start, stop, step = s.indices(len(self))
            for position in range(start, stop, step):
                pos = len(self) - position - 1
                if value: self.value |= (1 << pos)
                else: self.value &= ~(1 << pos)
            maximum_position = max((start + 1, stop, len(self)))
            self.length = maximum_position
        except:
            pos = len(self) - s - 1
            if value: self.value |= (1 << pos)
            else: self.value &= ~(1 << pos)
            if len(self) < pos: self.length = pos
        return self

    def __iter__(self):
        """Iterates over the values in the bitset."""
        for i in self[:]:
            yield i

    def __len__(self):
        """Returns the length of the bitset."""
        return self.length

- Emil

Answer 3

我不建议在生产代码中这样做，但是对于竞赛编程、面试准备和娱乐，人们应该熟悉位运算。

b = 0          # The empty bitset :)
b |= 1 << i    # Set
b & 1 << i     # Test
b &= ~(1 << i) # Reset
b ^= 1 << i    # Flip i
b = ~b         # Flip all

- YvesgereY

---

为什么这在生产代码中不被推荐？看起来简单而高效。 - Zachary HUANG

有些人可能认为这很晦涩，而且错别字很敏感！不过把它封装在一个类里就没问题了。 - YvesgereY

Answer 4

你可能想看一下我写的一个模块，叫做 bitstring （完整文档 在这里），虽然对于需要尽可能快速的简单情况，我仍然建议使用 bitarray。

一些类似的问题： Python中进行位域操作的最佳方法是什么？ Python是否有位域类型？ Python位流实现

- Scott Griffiths

Answer 5

如果位数是有限的，可以使用 enum.IntFlag 作为位集合。

请见 https://docs.python.org/3/howto/enum.html#intflag。

- Yang Bo