Bit manipulation
Bit manipulation is useful for things like creating bit sets (which are themselves useful for representing membership efficiently).
Formulae
Integers are represented using two’s complement, which simply means the opposite of an integer is calculated by inverting all of the bits and then adding 1:
where
Representing sets
Every subset of
represents
In python
members = 0
members |= 1 << 1
members |= 1 << 3
members |= 1 << 4
members |= 1 << 8
print("{0:032b}".format(members))
# 00000000000000000000000100011011
Set operations
Working with subsets
def all_subsets(n):
for b in range(1<<n):
print("{0:0b}".format(b))
def all_k_subsets(n):
for b in range(1<<n):
if bin(b).count('1'):
print("0:0b".format(b))
def all_subset_of(x):
b = 0
while (b-x) & x:
print("{0:0b}".format(b))
b = (b-x) & x
print("{0:0b}".format(x))