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 $0$ and capacity-1 (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 datastructures, 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.

class sage.misc.bitset.Bitset¶

Bases: sage.misc.bitset.FrozenBitset

A 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 $n$ natural numbers $0$ , $1$ , ..., $n-1$ (where $n$ , the capacity, can be specified), with typical set operations (intersection, union, symmetric difference, etc.). Secondly, a bitset can be thought of as a binary vector with typical binary operations (i.e., and, or, xor, etc.). This class supports both interfaces.

The interface in this class mirrors the interface in the set datatype of Python.

Warning

This class is most likely to be useful as a way to store Cython bitsets in Python datastructures, 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.

EXAMPLES:

sage: a=Bitset('1101')
sage: loads(dumps(a))==a
True
sage: a=Bitset('1101'*32)
sage: loads(dumps(a))==a
True

add(n)¶

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

clear()¶

Removes all elements from the set

EXAMPLES:

sage: a = Bitset('011')
sage: a.clear()
sage: a
000
sage: a = Bitset('011'*32)
sage: a.clear()
sage: set(a)
set([])

difference_update(other)¶

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

discard(n)¶

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]

intersection_update(other)¶

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

pop()¶

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()
...
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]

remove(n)¶

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)
...
KeyError: 2L
sage: a.remove(4)
...
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]

symmetric_difference_update(other)¶

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

update(other)¶

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

class sage.misc.bitset.FrozenBitset¶

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 $n$ natural numbers $0$ , $1$ , ..., $n-1$ (where $n$ , the capacity, can be specified), with typical set operations (intersection, union, symmetric difference, etc.). Secondly, a bitset can be thought of as a binary vector with typical binary operations (i.e., and, or, xor, etc.). This class supports both interfaces.

The interface in this class mirrors the interface in the frozenset datatype of Python.

Warning

This class is most likely to be useful as a way to store Cython bitsets in Python datastructures, 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.

EXAMPLES:

sage: a=FrozenBitset('1101')
sage: loads(dumps(a))==a
True

sage: a=FrozenBitset('1101'*64)
sage: loads(dumps(a))==a
True

capacity()¶

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

difference(other)¶

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

intersection(other)¶

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

isdisjoint(other)¶

Test to see if the 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

isempty()¶

Return True if the bitset is empty; False otherwise.

EXAMPLES:

sage: FrozenBitset().isempty()
True
sage: FrozenBitset([1]).isempty()
False
sage: FrozenBitset([],capacity=110).isempty()
True
sage: FrozenBitset(range(99)).isempty()
False

issubset(other)¶

Test to see if the 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

issuperset(other)¶

Test to see if the 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

symmetric_difference(other)¶

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

union(other)¶

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

A Python interface to the fast bitsets in Sage. Bitsets are fast¶

Previous topic

Next topic

This Page

Navigation

A Python interface to the fast bitsets in Sage. Bitsets are fast¶

Previous topic

Next topic

This Page

Quick search

Navigation