• Formulae
• Representing sets
• Set operations
• Working with subsets

Bit manipulation is useful for things like creating bit sets (which are themselves useful for representing membership efficiently).

Formulae

\(\&, \vert, ^\widehat{}\) are the and, or, and xor operations.

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 $\sim$ is the bit-inversion operator ( $ 10101 \rightarrow 01010 $ ). Simpler mnemonic is probably $ \sim x = -x -1 $.

\(x >> k\) means dividing $x$ by $2^k$ with truncation (rounding down) and \(x << k\) means multiplication by $2^k$. A bitmask is \(1 << k\), i.e. a word with $1$ in the $k$-th position of its bit representation.

Representing sets

Every subset of \(\left\{0, 1, 2, \dots, n - 1 \right\}\) can be represented by an $n$-bit integer whose $1$ bits indicate which element belongs to the set. For example, using a 32-bit integer

represents \(\left\{1, 3, 4, 8\right\}\)

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))