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

3 comments

Philippe 14 years, 9 months ago  # | flag

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  # | flag

@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  # | flag

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