Welcome, guest | Sign In | My Account | Store | Cart

This is a simple Bitset type for Python. It implements the Sequence interface plus __setitem__, the set operations, and string and integer conversions.

Python, 161 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161``` ```#! /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 ```

Philippe 14 years, 9 months ago

Geremy: This seems to be a decent implementation, but have you checked : link and link

Also you have full rights to license your recipe under any license you want but using the GPL 3 is not in the spirit and terms of this site.

See link that says "All submitted material will be made freely available on the ActiveState site under the MIT license." /hth

geremy condra (author) 14 years, 6 months ago

@Philippe

You're correct about the licensing. This was from a personal project that was under GPLv3 and I simply never changed that line- legally speaking, that pretty much doesn't mean anything anyway.

And yes, I have seen those implementations, and I essentially only chose to write my own because I'm working on Android and didn't want the hassle of packaging others' code.

Mark Lawrence 8 years, 3 months ago

Rather late but bare excepts, as Amy Winehouse sang in Rehab, no, no, no.

 Created by geremy condra on Mon, 4 May 2009 (MIT)