Bitmask subsets

Understand the idea

A mask represents a subset of n indexed items. Bit i says whether item i is selected. Enumerate 0..2^n-1; mask zero is the empty subset. Position identity matters when values repeat.

Work through an example

For [a,b], masks 00,01,10,11 represent [],[a],[b],[a,b]. The bit order can differ from printed character order, so label it.

Time and space complexity

Θ(n2^n) output construction/O(n) per temporary subset, plus all output storage.

Why it works

Each indexed subset has exactly one mask.

Common mistakes

• Masks with duplicate-valued positions may yield duplicate value lists.
• Exponential enumeration is unsuitable for large n.

Chapter lab · Python implementation

Bit operations treat an integer as binary positions. Our lab clears the lowest set bit repeatedly and enumerates subsets with masks. Examples use nonnegative integers unless an explicit width is supplied. Python integers are unbounded, so signed NOT and shifting differ from unsigned fixed-width machine examples.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def count_bits(value):
    if value<0: raise ValueError('nonnegative value required')
    count=0
    while value:
        value &= value-1
        count+=1
    return count

def subsets_mask(values):
    output=[]
    for mask in range(1<<len(values)):
        output.append([x for i,x in enumerate(values) if mask & (1<<i)])
    return output

def complement(value,width):
    if width<1 or not 0<=value<(1<<width):
        raise ValueError('value must fit width')
    return (~value)&((1<<width)-1)

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert count_bits(13)==3 and count_bits(0)==0
assert complement(5,4)==10
assert subsets_mask(['a','b'])==[[],['a'],['b'],['a','b']]
assert all(count_bits(x)==bin(x).count('1') for x in range(256))