Welcome, guest | Sign In | My Account | Store | Cart
```''' 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<<n)
def unsetbit(a, n): return a & ~(1<<n)
def toggle(a, n): return a ^ (1<<n)

# Append and pop will add or remove a bit from the end of the array:
def append(a, v): return (a<<1) | v
def pop(a):
v = (a & 1)
new_a = (a >> 1)
return new_a, v

# Query a bitarray:
def getbit(a, n): return a & (1<<n)
def countbits(a): return bin(a).count('1')
def activebits(a):
s=bin(a)[2:][::-1]
return [i for i,d in enumerate(s) if d == '1']
def tostring(a, w=0): return bin(a)[2:].zfill(w)

# Convert bit arrays for storage in files or databases:
import cPickle
def store(a): return cPickle.dumps(a, -1)

def _analyticsdemo():
USERS = 1000000
from random import randint

def randarray(n,arr=0):
for i in xrange(n):
arr = setbit(arr, randint(0, USERS-1))
return arr