Bitsets
A Python interface to the fast bitsets in Sage. Bitsets are fast
binary sets that store elements by toggling bits in an array of
numbers. A bitset can store values between and capacity - 1,
inclusive (where capacity is finite, but arbitrary). The storage cost is
linear in capacity.
Warning
This class is most likely to be useful as a way to store Cython bitsets in Python data structures, acting on them using the Cython inline functions. If you want to use these classes for a Python set type, the Python set or frozenset data types may be faster.
Bases: sage.misc.bitset.FrozenBitset
A bitset class which leverages inline Cython functions for creating and manipulating bitsets. See the class documentation of FrozenBitset for details on the parameters of the constructor and how to interpret the string representation of a Bitset.
A bitset can be thought of in two ways. First, as a set of elements
from the universe of the natural numbers
(where
the capacity
can be specified), with typical set operations such as
intersection, union, symmetric difference, etc. Secondly, a bitset can
be thought of as a binary vector with typical binary operations such as
and, or, xor, etc. This class supports both interfaces.
The interface in this class mirrors the interface in the set data type of Python.
Warning
This class is most likely to be useful as a way to store Cython bitsets in Python data structures, acting on them using the Cython inline functions. If you want to use this class for a Python set type, the Python set data type may be faster.
See also
EXAMPLES:
sage: a = Bitset('1101')
sage: loads(dumps(a)) == a
True
sage: a = Bitset('1101' * 32)
sage: loads(dumps(a)) == a
True
Update the bitset by adding n.
EXAMPLES:
sage: a = Bitset('110')
sage: a.add(5)
sage: a
110001
sage: a.add(100)
sage: sorted(list(a))
[0, 1, 5, 100]
sage: a.capacity()
101
TESTS:
The input n must be an integer.
sage: Bitset('110').add(None)
Traceback (most recent call last):
...
TypeError: an integer is required
Removes all elements from the bitset.
EXAMPLES:
sage: a = Bitset('011')
sage: a.clear()
sage: a
000
sage: a = Bitset('011' * 32)
sage: a.clear()
sage: set(a)
set([])
Update the bitset to the difference of self and other.
EXAMPLES:
sage: a = Bitset('110')
sage: a.difference_update(Bitset('0101'))
sage: a
1000
sage: a_set = set(a)
sage: a.difference_update(FrozenBitset('010101' * 10)); a
100000000000000000000000000000000000000000000000000000000000
sage: a_set.difference_update(FrozenBitset('010101' * 10))
sage: a_set == set(a)
True
sage: a.difference_update(FrozenBitset('110'))
sage: a_set.difference_update(FrozenBitset('110'))
sage: a_set == set(a)
True
sage: a.difference_update(FrozenBitset('01010' * 20)); a
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
sage: a_set.difference_update(FrozenBitset('01010' * 20))
sage: a_set == set(a)
True
sage: b = Bitset('10101' * 20)
sage: b_set = set(b)
sage: b.difference_update(FrozenBitset('1' * 5)); b
0000010101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101
sage: b_set.difference_update(FrozenBitset('1' * 5))
sage: b_set == set(b)
True
TESTS:
sage: Bitset('110').difference_update(None)
Traceback (most recent call last):
...
TypeError: other cannot be None
Update the bitset by removing n.
EXAMPLES:
sage: a = Bitset('110')
sage: a.discard(1)
sage: a
100
sage: a.discard(2)
sage: a.discard(4)
sage: a
100
sage: a = Bitset('000001' * 15); sorted(list(a))
[5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89]
sage: a.discard(83); sorted(list(a))
[5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 89]
sage: a.discard(82); sorted(list(a))
[5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 89]
TESTS:
The input n must be an integer.
sage: Bitset('110').discard(None)
Traceback (most recent call last):
...
TypeError: an integer is required
Update the bitset to the intersection of self and other.
EXAMPLES:
sage: a = Bitset('110')
sage: a.intersection_update(Bitset('0101'))
sage: a
0100
sage: a_set = set(a)
sage: a.intersection_update(Bitset('0110' * 25))
sage: a
0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
sage: a_set.intersection_update(Bitset('0110' * 25))
sage: set(a) == a_set
True
TESTS:
sage: Bitset('110').intersection_update(None)
Traceback (most recent call last):
...
TypeError: other cannot be None
Remove and return an arbitrary element from the set. Raises KeyError if the set is empty.
EXAMPLES:
sage: a = Bitset('011')
sage: a.pop()
1
sage: a
001
sage: a.pop()
2
sage: a
000
sage: a.pop()
Traceback (most recent call last):
...
KeyError: 'pop from an empty set'
sage: a = Bitset('0001'*32)
sage: a.pop()
3
sage: [a.pop() for _ in range(20)]
[7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83]
Update the bitset by removing n. Raises KeyError if n is not contained in the bitset.
EXAMPLES:
sage: a = Bitset('110')
sage: a.remove(1)
sage: a
100
sage: a.remove(2)
Traceback (most recent call last):
...
KeyError: 2L
sage: a.remove(4)
Traceback (most recent call last):
...
KeyError: 4L
sage: a
100
sage: a = Bitset('000001' * 15); sorted(list(a))
[5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 83, 89]
sage: a.remove(83); sorted(list(a))
[5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, 77, 89]
TESTS:
The input n must be an integer.
sage: Bitset('110').remove(None)
Traceback (most recent call last):
...
TypeError: an integer is required
Update the bitset to the symmetric difference of self and other.
EXAMPLES:
sage: a = Bitset('110')
sage: a.symmetric_difference_update(Bitset('0101'))
sage: a
1001
sage: a_set = set(a)
sage: a.symmetric_difference_update(FrozenBitset('010101' * 10)); a
110001010101010101010101010101010101010101010101010101010101
sage: a_set.symmetric_difference_update(FrozenBitset('010101' * 10))
sage: a_set == set(a)
True
sage: a.symmetric_difference_update(FrozenBitset('01010' * 20)); a
1001011111000001111100000111110000011111000001111100000111110101001010010100101001010010100101001010
sage: a_set.symmetric_difference_update(FrozenBitset('01010' * 20))
sage: a_set == set(a)
True
sage: b = Bitset('10101' * 20)
sage: b_set = set(b)
sage: b.symmetric_difference_update( FrozenBitset('1' * 5)); b
0101010101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101
sage: b_set.symmetric_difference_update( FrozenBitset('1' * 5))
sage: b_set == set(b)
True
TESTS:
sage: Bitset('110').symmetric_difference_update(None)
Traceback (most recent call last):
...
TypeError: other cannot be None
Update the bitset to include items in other.
EXAMPLES:
sage: a = Bitset('110')
sage: a.update(Bitset('0101'))
sage: a
1101
sage: a_set = set(a)
sage: a.update(Bitset('00011' * 25))
sage: a
11011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011
sage: a_set.update(Bitset('00011' * 25))
sage: set(a) == a_set
True
TESTS:
During update, other cannot be None.
sage: a = Bitset('1101')
sage: a.update(None)
Traceback (most recent call last):
...
TypeError: other cannot be None
Bases: object
A frozen bitset class which leverages inline Cython functions for creating and manipulating bitsets.
A bitset can be thought of in two ways. First, as a set of elements
from the universe of the natural numbers
(where
the capacity
can be specified), with typical set operations such as
intersection, union, symmetric difference, etc. Secondly, a bitset can
be thought of as a binary vector with typical binary operations such as
and, or, xor, etc. This class supports both interfaces.
The interface in this class mirrors the interface in the frozenset data type of Python. See the Python documentation on set types for more details on Python’s set and frozenset classes.
Warning
This class is most likely to be useful as a way to store Cython bitsets in Python data structures, acting on them using the Cython inline functions. If you want to use this class for a Python set type, the Python frozenset data type may be faster.
INPUT:
OUTPUT:
The string representation of a FrozenBitset FB can be
understood as follows. Let be the string
representation of the bitset FB, where each
. We
read the
from left to right. If
, then the nonnegative
integer
is in the bitset FB. Similarly, if
, then
is not in FB. In other words, FB is a subset of
and the membership in FB of each
is
determined by the binary value
.
EXAMPLES:
The default bitset, which has capacity 1:
sage: FrozenBitset()
0
sage: FrozenBitset(None)
0
Trying to create an empty bitset fails:
sage: FrozenBitset([])
Traceback (most recent call last):
...
ValueError: Bitsets must not be empty
sage: FrozenBitset(list())
Traceback (most recent call last):
...
ValueError: Bitsets must not be empty
sage: FrozenBitset(())
Traceback (most recent call last):
...
ValueError: Bitsets must not be empty
sage: FrozenBitset(tuple())
Traceback (most recent call last):
...
ValueError: Bitsets must not be empty
sage: FrozenBitset("")
Traceback (most recent call last):
...
ValueError: Bitsets must not be empty
We can create the all-zero bitset as follows:
sage: FrozenBitset(capacity=10)
0000000000
sage: FrozenBitset([], capacity=10)
0000000000
We can initialize a FrozenBitset with a Bitset or another FrozenBitset, and compare them for equality. As they are logically the same bitset, the equality test should return True. Furthermore, each bitset is a subset of the other.
sage: def bitcmp(a, b, c): # custom function for comparing bitsets
....: print(a == b == c)
....: print(a <= b, b <= c, a <= c)
....: print(a >= b, b >= c, a >= c)
....: print(a != b, b != c, a != c)
sage: a = Bitset("1010110"); b = FrozenBitset(a); c = FrozenBitset(b)
sage: a; b; c
1010110
1010110
1010110
sage: a < b, b < c, a < c
(False, False, False)
sage: a > b, b > c, a > c
(False, False, False)
sage: bitcmp(a, b, c)
True
(True, True, True)
(True, True, True)
(False, False, False)
Try a random bitset:
sage: a = Bitset(randint(0, 1) for n in range(1, randint(1, 10^4)))
sage: b = FrozenBitset(a); c = FrozenBitset(b)
sage: bitcmp(a, b, c)
True
(True, True, True)
(True, True, True)
(False, False, False)
A bitset with a hard-coded bitstring:
sage: FrozenBitset('101')
101
For a string, only those positions with 1 would be initialized to 1 in the corresponding position in the bitset. All other characters in the string, including 0, are set to 0 in the resulting bitset.
sage: FrozenBitset('a')
0
sage: FrozenBitset('abc')
000
sage: FrozenBitset('abc1')
0001
sage: FrozenBitset('0abc1')
00001
sage: FrozenBitset('0abc10')
000010
sage: FrozenBitset('0a*c10')
000010
Represent the first 10 primes as a bitset. The primes are stored as a list and as a tuple. We then recover the primes from its bitset representation, and query the bitset for its length (how many elements it contains) and whether an element is in the bitset. Note that the length of a bitset is different from its capacity. The length counts the number of elements currently in the bitset, while the capacity is the number of elements that the bitset can hold.
sage: p = primes_first_n(10); p
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
sage: tuple(p)
(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
sage: F = FrozenBitset(p); F; FrozenBitset(tuple(p))
001101010001010001010001000001
001101010001010001010001000001
Recover the primes from the bitset:
sage: for b in F:
....: print b,
2 3 5 7 11 13 17 19 23 29
sage: list(F)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Query the bitset:
sage: len(F)
10
sage: len(list(F))
10
sage: F.capacity()
30
sage: s = str(F); len(s)
30
sage: 2 in F
True
sage: 1 in F
False
A random iterable, with all duplicate elements removed:
sage: L = [randint(0, 100) for n in range(1, randint(1, 10^4))]
sage: FrozenBitset(L) == FrozenBitset(list(set(L)))
True
sage: FrozenBitset(tuple(L)) == FrozenBitset(tuple(set(L)))
True
TESTS:
Loading and dumping objects:
sage: a = FrozenBitset('1101')
sage: loads(dumps(a)) == a
True
sage: a = FrozenBitset('1101' * 64)
sage: loads(dumps(a)) == a
True
If iter is a nonempty string and capacity is specified, then capacity must match the number of elements in iter:
sage: FrozenBitset("110110", capacity=3)
Traceback (most recent call last):
...
ValueError: bitset capacity does not match passed string
sage: FrozenBitset("110110", capacity=100)
Traceback (most recent call last):
...
ValueError: bitset capacity does not match passed string
The parameter capacity must be positive:
sage: FrozenBitset("110110", capacity=0)
Traceback (most recent call last):
...
ValueError: bitset capacity must be greater than 0
sage: FrozenBitset("110110", capacity=-2)
Traceback (most recent call last):
...
OverflowError: can't convert negative value to unsigned long
Return the size of the underlying bitset.
The maximum value that can be stored in the current underlying bitset is self.capacity() - 1.
EXAMPLES:
sage: FrozenBitset('11000').capacity()
5
sage: FrozenBitset('110' * 32).capacity()
96
sage: FrozenBitset(range(20), capacity=450).capacity()
450
Return the complement of self.
EXAMPLES:
sage: ~FrozenBitset('10101')
01010
sage: ~FrozenBitset('11111'*10)
00000000000000000000000000000000000000000000000000
sage: x = FrozenBitset('10'*40)
sage: x == ~x
False
sage: x == ~~x
True
sage: x|(~x) == FrozenBitset('11'*40)
True
sage: ~x == FrozenBitset('01'*40)
True
Return the difference of self and other.
EXAMPLES:
sage: FrozenBitset('10101').difference(FrozenBitset('11100'))
00001
sage: FrozenBitset('11111' * 10).difference(FrozenBitset('010101' * 10))
101010101010101010101010101010101010101010101010100000000000
TESTS:
sage: set(FrozenBitset('11111' * 10).difference(FrozenBitset('010101' * 10))) == set(FrozenBitset('11111' * 10)).difference(FrozenBitset('010101' * 10))
True
sage: set(FrozenBitset('1' * 5).difference(FrozenBitset('01010' * 20))) == set(FrozenBitset('1' * 5)).difference(FrozenBitset('01010' * 20))
True
sage: set(FrozenBitset('10101' * 20).difference(FrozenBitset('1' * 5))) == set(FrozenBitset('10101' * 20)).difference(FrozenBitset('1' * 5))
True
sage: FrozenBitset('10101').difference(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Return the intersection of self and other.
EXAMPLES:
sage: FrozenBitset('10101').intersection(FrozenBitset('11100'))
10100
sage: FrozenBitset('11111' * 10).intersection(FrozenBitset('010101' * 10))
010101010101010101010101010101010101010101010101010000000000
TESTS:
sage: set(FrozenBitset('11111' * 10).intersection(FrozenBitset('010101' * 10))) == set(FrozenBitset('11111' * 10)).intersection(FrozenBitset('010101' * 10))
True
sage: set(FrozenBitset('1' * 5).intersection(FrozenBitset('01010' * 20))) == set(FrozenBitset('1' * 5)).intersection(FrozenBitset('01010' * 20))
True
sage: set(FrozenBitset('10101' * 20).intersection(FrozenBitset('1' * 5))) == set(FrozenBitset('10101' * 20)).intersection(FrozenBitset('1' * 5))
True
sage: FrozenBitset("101011").intersection(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Test to see if self is disjoint from other.
EXAMPLES:
sage: FrozenBitset('11').isdisjoint(FrozenBitset('01'))
False
sage: FrozenBitset('01').isdisjoint(FrozenBitset('001'))
True
sage: FrozenBitset('00101').isdisjoint(FrozenBitset('110' * 35))
False
TESTS:
sage: FrozenBitset('11').isdisjoint(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Test if the bitset is empty.
INPUT:
OUTPUT:
EXAMPLES:
sage: FrozenBitset().isempty()
True
sage: FrozenBitset([1]).isempty()
False
sage: FrozenBitset([], capacity=110).isempty()
True
sage: FrozenBitset(range(99)).isempty()
False
Test to see if self is a subset of other.
EXAMPLES:
sage: FrozenBitset('11').issubset(FrozenBitset('01'))
False
sage: FrozenBitset('01').issubset(FrozenBitset('11'))
True
sage: FrozenBitset('01').issubset(FrozenBitset('01' * 45))
True
TESTS:
sage: FrozenBitset('11').issubset(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Test to see if self is a superset of other.
EXAMPLES:
sage: FrozenBitset('11').issuperset(FrozenBitset('01'))
True
sage: FrozenBitset('01').issuperset(FrozenBitset('11'))
False
sage: FrozenBitset('01').issuperset(FrozenBitset('10' * 45))
False
TESTS:
sage: FrozenBitset('11').issuperset(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Return the symmetric difference of self and other.
EXAMPLES:
sage: FrozenBitset('10101').symmetric_difference(FrozenBitset('11100'))
01001
sage: FrozenBitset('11111' * 10).symmetric_difference(FrozenBitset('010101' * 10))
101010101010101010101010101010101010101010101010100101010101
TESTS:
sage: set(FrozenBitset('11111' * 10).symmetric_difference(FrozenBitset('010101' * 10))) == set(FrozenBitset('11111' * 10)).symmetric_difference(FrozenBitset('010101' * 10))
True
sage: set(FrozenBitset('1' * 5).symmetric_difference(FrozenBitset('01010' * 20))) == set(FrozenBitset('1' * 5)).symmetric_difference(FrozenBitset('01010' * 20))
True
sage: set(FrozenBitset('10101' * 20).symmetric_difference(FrozenBitset('1' * 5))) == set(FrozenBitset('10101' * 20)).symmetric_difference(FrozenBitset('1' * 5))
True
sage: FrozenBitset('11111' * 10).symmetric_difference(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Return the union of self and other.
EXAMPLES:
sage: FrozenBitset('10101').union(FrozenBitset('11100'))
11101
sage: FrozenBitset('10101' * 10).union(FrozenBitset('01010' * 10))
11111111111111111111111111111111111111111111111111
TESTS:
sage: set(FrozenBitset('10101' * 10).union(FrozenBitset('01010' * 10))) == set(FrozenBitset('10101' * 10)).union(FrozenBitset('01010' * 10))
True
sage: set(FrozenBitset('10101').union(FrozenBitset('01010' * 20))) == set(FrozenBitset('10101')).union(FrozenBitset('01010' * 20))
True
sage: set(FrozenBitset('10101' * 20).union(FrozenBitset('01010'))) == set(FrozenBitset('10101' * 20)).union(FrozenBitset('01010'))
True
sage: FrozenBitset('10101' * 10).union(None)
Traceback (most recent call last):
...
ValueError: other cannot be None
Test the Cython bitset functions so we can have some relevant doctests.
TESTS:
sage: from sage.misc.bitset import test_bitset
sage: test_bitset('00101', '01110', 4)
a 00101
list a [2, 4]
a.size 5
len(a) 2
a.limbs 1
b 01110
a.in(n) True
a.not_in(n) False
a.add(n) 00101
a.discard(n) 00100
a.set_to(n) 00101
a.flip(n) 00100
a.set_first_n(n) 11110
a.first_in_complement() 4
a.isempty() False
a.eq(b) False
a.cmp(b) 1
a.lex_cmp(b) -1
a.issubset(b) False
a.issuperset(b) False
a.copy() 00101
r.clear() 00000
complement a 11010
a intersect b 00100
a union b 01111
a minus b 00001
a symmetric_difference b 01011
a.rshift(n) 10000
a.lshift(n) 00000
a.first() 2
a.next(n) 4
a.first_diff(b) 1
a.next_diff(b, n) 4
a.hamming_weight() 2
a.map(m) 10100
a == loads(dumps(a)) True
reallocating a 00101
to size 4 0010
to size 8 00100000
to original size 00100
sage: test_bitset('11101', '11001', 2)
a 11101
list a [0, 1, 2, 4]
a.size 5
len(a) 4
a.limbs 1
b 11001
a.in(n) True
a.not_in(n) False
a.add(n) 11101
a.discard(n) 11001
a.set_to(n) 11101
a.flip(n) 11001
a.set_first_n(n) 11000
a.first_in_complement() 2
a.isempty() False
a.eq(b) False
a.cmp(b) 1
a.lex_cmp(b) 1
a.issubset(b) False
a.issuperset(b) True
a.copy() 11101
r.clear() 00000
complement a 00010
a intersect b 11001
a union b 11101
a minus b 00100
a symmetric_difference b 00100
a.rshift(n) 10100
a.lshift(n) 00111
a.first() 0
a.next(n) 2
a.first_diff(b) 2
a.next_diff(b, n) 2
a.hamming_weight() 4
a.map(m) 10111
a == loads(dumps(a)) True
reallocating a 11101
to size 2 11
to size 4 1100
to original size 11000
Test a corner-case: a bitset that is a multiple of words:
sage: test_bitset('00'*64, '01'*64, 127)
a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
list a []
a.size 128
len(a) 0
a.limbs ...
b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
a.in(n) False
a.not_in(n) True
a.add(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
a.discard(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a.set_to(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
a.flip(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
a.set_first_n(n) 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
a.first_in_complement() 127
a.isempty() True
a.eq(b) False
a.cmp(b) -1
a.lex_cmp(b) -1
a.issubset(b) True
a.issuperset(b) False
a.copy() 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
r.clear() 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
complement a 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
a intersect b 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a union b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
a minus b 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a symmetric_difference b 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
a.rshift(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a.lshift(n) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a.first() -1
a.next(n) -1
a.first_diff(b) 1
a.next_diff(b, n) 127
a.hamming_weight() 0
a.map(m) 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
a == loads(dumps(a)) True
rshifts add True
lshifts add True
intersection commutes True
union commutes True
not not = id True
flipped bit 127
add bit 127
discard bit 127
lshift add unset ok True
rshift set unset ok True
reallocating a 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
to size 127 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
to size 254 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
to original size 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Large enough to span multiple limbs. We don’t explicitly check the number of limbs below because it will be different in the 32 bit versus 64 bit cases:
sage: test_bitset('111001'*25, RealField(151)(pi).str(2)[2:], 69)
a 111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001
list a [0, 1, 2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20, 23, 24, 25, 26, 29, 30, 31, 32, 35, 36, 37, 38, 41, 42, 43, 44, 47, 48, 49, 50, 53, 54, 55, 56, 59, 60, 61, 62, 65, 66, 67, 68, 71, 72, 73, 74, 77, 78, 79, 80, 83, 84, 85, 86, 89, 90, 91, 92, 95, 96, 97, 98, 101, 102, 103, 104, 107, 108, 109, 110, 113, 114, 115, 116, 119, 120, 121, 122, 125, 126, 127, 128, 131, 132, 133, 134, 137, 138, 139, 140, 143, 144, 145, 146, 149]
a.size 150
len(a) 100
a.limbs ...
b 000100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111
a.in(n) False
a.not_in(n) True
a.add(n) 111001111001111001111001111001111001111001111001111001111001111001111101111001111001111001111001111001111001111001111001111001111001111001111001111001
a.discard(n) 111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001
a.set_to(n) 111001111001111001111001111001111001111001111001111001111001111001111101111001111001111001111001111001111001111001111001111001111001111001111001111001
a.flip(n) 111001111001111001111001111001111001111001111001111001111001111001111101111001111001111001111001111001111001111001111001111001111001111001111001111001
a.set_first_n(n) 111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
a.first_in_complement() 69
a.isempty() False
a.eq(b) False
a.cmp(b) -1
a.lex_cmp(b) 1
a.issubset(b) False
a.issuperset(b) False
a.copy() 111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001
r.clear() 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
complement a 000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110000110
a intersect b 000000100001111000110001010001000000001001010001100001000000100000001001100001001000010000010001000000011001100000111001101000100001001000000000100001
a union b 111101111001111111111101111001111101111011111001111001111111111111111001111011111101111101111111111001111011111001111001111001111101111001111101111111
a minus b 111001011000000001001000101000111001110000101000011000111001011001110000011000110001101001101000111001100000011001000000010001011000110001111001011000
a symmetric_difference b 111101011000000111001100101000111101110010101000011000111111011111110000011010110101101101101110111001100010011001000000010001011100110001111101011110
a.rshift(n) 001111001111001111001111001111001111001111001111001111001111001111001111001111001000000000000000000000000000000000000000000000000000000000000000000000
a.lshift(n) 000000000000000000000000000000000000000000000000000000000000000000000111001111001111001111001111001111001111001111001111001111001111001111001111001111
a.first() 0
a.next(n) 71
a.first_diff(b) 0
a.next_diff(b, n) 73
a.hamming_weight() 100
a.map(m) 100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111100111
a == loads(dumps(a)) True
rshifts add True
lshifts add True
intersection commutes True
union commutes True
not not = id True
flipped bit 69
add bit 69
discard bit 69
lshift add unset ok True
rshift set unset ok True
reallocating a 111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001111001
to size 69 111001111001111001111001111001111001111001111001111001111001111001111
to size 138 111001111001111001111001111001111001111001111001111001111001111001111000000000000000000000000000000000000000000000000000000000000000000000
to original size 111001111001111001111001111001111001111001111001111001111001111001111000000000000000000000000000000000000000000000000000000000000000000000000000000000
Tests for the bitset_pop function.
TESTS:
sage: from sage.misc.bitset import test_bitset_pop
sage: test_bitset_pop('0101')
a.pop() 1
new set: 0001
sage: test_bitset_pop('0000')
Traceback (most recent call last):
...
KeyError: 'pop from an empty set'
Test the bitset_remove function.
TESTS:
sage: from sage.misc.bitset import test_bitset_remove
sage: test_bitset_remove('01', 0)
Traceback (most recent call last):
...
KeyError: 0L
sage: test_bitset_remove('01', 1)
a 01
a.size 2
a.limbs 1
n 1
a.remove(n) 00
Test the bitset function set_first_n.
TESTS:
sage: from sage.misc.bitset import test_bitset_set_first_n
sage: test_bitset_set_first_n('00'*64, 128)
a.set_first_n(n) 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
This (artificially) tests pickling of bitsets across systems.
INPUT:
OUTPUT:
A list form of the bitset corresponding to the pickled data.
EXAMPLES:
We compare 64-bit and 32-bit encoding. Both should unpickle on any system:
sage: from sage.misc.bitset import test_bitset_unpickle
sage: test_bitset_unpickle((0, 100, 2, 8, (33, 6001)))
[0, 5, 64, 68, 69, 70, 72, 73, 74, 76]
sage: test_bitset_unpickle((0, 100, 4, 4, (33, 0, 6001, 0)))
[0, 5, 64, 68, 69, 70, 72, 73, 74, 76]