## Posted on 2023-06-30 15:31

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