''' Bit Array - Bit array computing with long integers.
Good for around 1,000,000 bit arrays but gets slow with a billion bits...
Mike Sweeney. June 2013.
Positives:
Works even with old versions of Python.
Only pure Python needed - no third party modules.
Binary operations such as & | ^ << and >> are fast.
Store and load are fast and compact.
Negatives:
Longs are passed by value so no in-place operations are possible.
Array changing operations are slow on large arrays.
Timing of one AND operation on bit arrays with Python 2.7 on AMD 3.8 GHz 4 core:
1,000,000 bit 15 us
10,000,000 bit 320 us
100,000,000 bit 6.2 ms
1,000,000,000 bit 86 ms (125MB bit array objects)
'''
# Constructors for bit arrays:
bitarray = long
def frombin(s): return int(s, 2)
# Operations on bit arrays of the same size:
def issubset(a, b): return a & b == a
def subtract(a, b): return a & ~b
# use & | ^ and ~ for other bitarray operations
# Change a bit value in a bit array:
def setbit(a, n): return a | (1<> 1)
return new_a, v
# Query a bitarray:
def getbit(a, n): return a & (1<