Set operations using bit arrays

Let $X, Y \subseteq \lbrace 0, 1, \ldots, N \rbrace$. These sets can be written in equivalent form as bit arrays of size $N + 1$. Let $x$ be the bit array form of $X$ (and similarly, $y$ of $Y$): the bit $x_i$ is flipped iff $i \in X$, and not set otherwise (where $i \in \lbrace 0, \ldots, N \rbrace$). Such bit arrays enable the following set operations:

• The membership test of $i \in X$ is given by (x >> i) & 1.
• The complement $X^\complement$ is given by ~x.
• The intersection $X \cap Y$ is given by x & y.
• The union $X \cup Y$ is given by x | y.
• The relative complement $X \setminus Y$ is given by x & ~y.
• The symmetric difference $X~\Delta~Y$ is given by (x & ~y) | (y & ~x), which is equivalent to x ^ y.

These operations can be performed very efficiently in hardware, which sometimes offers substantial performance gains over other approaches (e.g., those based on hash sets).