Assign membership to bit positions
Fix the universe to integers from zero through nine. Element i belongs to the set exactly when bit i is one. Set A containing zero, three and nine therefore has three selected positions. A tiny element count does not imply a tiny direct bit representation: three IDs near a billion still require a very large universe unless a separate mapping compresses them.
Bitsets combine many memberships with word-level operations, but every participant must agree on position meaning. Renumbering product IDs can make identical bits represent different products. This example uses fixed small integer IDs and rejects out-of-universe values. If external IDs are mapped into positions, preserve that dictionary and its version alongside the bitset. Element count, universe size and representation identity are separate concerns.
Verify union, intersection and bounded complement
With B containing three and four, A OR B represents zero, three, four and nine, while A AND B contains only three. Difference keeps positions belonging to A but not B. A complement must be bounded to the declared universe. Python's plain bitwise NOT produces a negative integer, not a finite ten-element complement; mask it to the lower ten bits.
Difference is directional: A minus B need not equal B minus A. A full complement can also be expressed by exclusive OR with the universe mask when all bits are valid. Check the four possibilities of membership in A and B at one position. The correspondence between set logic and the bit-operation truth table explains the formulas more clearly than treating them as unrelated programming tricks.
| In A | In B | In A minus B |
|---|---|---|
| No | No | No |
| No | Yes | No |
| Yes | No | Yes |
| Yes | Yes | No |
Mask unused tail positions
A sixty-four-bit word holding a ten-element universe has fifty-four unused upper positions. If complement leaves those bits set, population count invents nonexistent members. The last word needs the same treatment in a multiword representation whenever universe size is not a word multiple. A masked Python integer demonstrates the boundary without requiring a separate array-of-words implementation.
A fixed-width port must also check language rules for shifts at or beyond the type width. Python's arbitrary-size integers do not share every complement and shifting rule with C or C++. Reason first about the abstract universe, then about the chosen integer representation. Removing range checks is only valid when another explicit boundary enforces the input contract; an invalid position must not silently become a valid member.
Exhaust a small universe
The code checks every pair of six-bit values, sixty-four times sixty-four or 4,096 cases. Convert those memberships into ordinary Python sets and compare intersection and difference. The ten-bit complement example must have seven members because A occupies three of ten positions. Printed binary strings may display high bits on the left, so use numeric position labels when checking correspondence.
Setting the same member twice leaves membership unchanged. Inserting element ten into width ten raises ValueError. This example uses a fixed positive width. A reusable library would additionally validate the width's type, negative values and excessive allocation requests. The tests establish the stated small-universe operations, not every resource-management policy that a public bitset API would need.
def bits(values,width):
result=0
for value in values:
if not 0<=value<width:raise ValueError('outside universe')
result|=1<<value
return result
width=10;mask=(1<<width)-1
A=bits([0,3,9],width);B=bits([3,4],width)
assert A&B==bits([3],width)
assert A|B==bits([0,3,4,9],width)
assert A&(~B&mask)==bits([0,9],width)
assert (~A&mask).bit_count()==7
for a in range(1<<6):
for b in range(1<<6):
x={i for i in range(6) if a>>i&1};y={i for i in range(6) if b>>i&1}
assert a&b==bits(x&y,6)
assert a&(~b&63)==bits(x-y,6)
try:bits([10],10)
except ValueError:pass
else:raise AssertionError('range check missing')
print('4096 pairs checked; complement masked to width')
Count words rather than naming one instruction
For universe size U and machine word width w, a fixed-word-array set operation typically costs O(ceil(U divided by w)). It is constant only when the relevant universe fits a bounded number of words. Python integer AND likewise processes internal digits as needed; it does not promise one hardware instruction for arbitrary universe size.
Enumeration adds output cost. Scanning every position and repeatedly removing the lowest set bit have different operation counts, and each still needs to emit the requested members. Separate word operations, universe size and result size. Bitsets can be attractive for repeated intersections over a dense bounded universe, while sparse enormous ID spaces may favor sorted lists or hash sets. The storage contract determines whether bulk logical operations actually provide a useful tradeoff.
Include representation conversion in comparisons
A universe of one thousand uses 125 logical bit bytes before object overhead. With nine hundred members, that may be compact relative to storing individual integers. A billion-position universe with only two members instead needs roughly 125 megabytes as a direct bitmap. Logical bytes and actual allocated-object sizes remain different measurements.
Compressing IDs to consecutive positions can reduce the universe, but building and retaining the conversion dictionary has its own cost. New IDs and cross-process exchange must preserve the same mapping. A benchmark should say whether it measures only AND on already converted bitsets or the complete path from external IDs through conversion and back to result IDs. A fast primitive does not automatically make the surrounding application fast or memory efficient.
Define width compatibility at the API boundary
Two bitsets must agree on universe width and ID mapping before combining. Integer AND may execute for widths eight and ten, but complement and enumeration semantics remain ambiguous. Choose an explicit widening or rejection rule.
A serialized format also defines bit order, word endianness and unused tail positions. One matching printed integer does not prove cross-language compatibility. Round-trip tests at position zero, the final valid position and both sides of a word boundary help detect shifted or reversed mappings. Representation compatibility is separate from correctness of the logical AND primitive.
Exercise: solve a bounded complement exercise
For universe zero through seven, A containing one and six, and B containing zero, one and seven, the intersection is one, A minus B is six, and A's complement is zero, two, three, four, five and seven. The mask is 255, not an unbounded sequence of inverted bits. Reversing the difference gives zero and seven. Check positions, not just cardinalities.
Expand the universe to zero through nine without changing A or B. Intersection and difference stay the same, but A's complement gains eight and nine. Complement depends on the universe even when stored memberships do not change. This explains why a serialized bitset needs its width or universe identity. Keep member count, universe size, word count and actual memory allocation distinct when comparing representations.