Classic Set Operations

Because we’re talking about sets, it’s worth highlighting some of the most common set operations. These are the operations known as union, intersection, and difference. To keep things simple, I’ll demo these operations using single integers as bit vectors, rather than using an array of integers.

Union

The union of two sets is a third set that contains all the values from the first two sets combined. For example:

	Set A: {0, 3, 7}
	Set B: {2, 3, 6}

	Union: {0, 2, 3, 6, 7}

Note that the value 3 only appears once in the union. Although both Set A and Set B contain a 3, the union set contains only one instance of 3. This again is because a set, by definition, does not hold duplicate values.

Thanks to bitwise operators, it’s easy and fast to find the union of bit vector sets. All we have to do is OR the two bit vectors together:

	Set A: 10001001
	Set B: 01001100

	A \| B = 11001101

That is, the OR operation will produce a 1 bit at any bit index where either bit vector has a 1 bit. This is the union of the two bit vectors.

Intersection

The intersection of two sets is a third set that contains only the values that the first two sets have in common:

	Set A: {0, 3, 7}
	Set B: {2, 3, 6}

	Intersection: {3}

We can find the intersection of two bit vectors with a simple AND operation:

	Set A: 10001001
	Set B: 01001100

	A & B = 00001000

The AND operation informs us where both bit vectors share a 1 bit. It is only the values represented by these 1 bits that get included in the intersection set.

Let’s look at one more operation.

Difference

The difference between two sets is a third set that contains all items from the first set minus intersecting items from the second set:

	Set A: 10001001 -> {0, 3, 7}
	Set B: 01001100 -> {2, 3, 6}

	Difference of A minus B: 10000001 -> {0, 7}

Here, the difference is identical to Set A, except that we removed the 3 since Set B also contains a 3.

Interestingly, we can compute the difference between Set A and Set B by ANDing A with the inverse of Set B. That is, we run the code: A & ~B. Here’s what this looks like:

	Set A: 10001001
	Inverse of Set B: 10110011

	A & ~B = 10000001

Here’s why this works. Our goal can be broken down into three subgoals:

Subgoal #1: Our result integer should have the same 0 bits that Set A does. (This is because the result set should not contain any values that Set A doesn’t have.)
Subgoal #2: If both Set A and Set B share a 1 bit at a particular digit place, the result should have a 0 bit at that place. (This is the subtraction of Set B from Set A.)
Subgoal #3: At any place where Set A has a 1 bit, and Set B has a 0 bit, the result should have a 1 bit at that place. (These are the values of Set A that do not get subtracted out.)

Here’s how we achieve these three subgoals with the trick of A & ~B.

Subgoal #1 is accomplished because when we AND a 0 bit from Set A with any other bit, the result will always be a 0 bit.

We take care of Subgoal #2 because by inverting Set B, we turn all of its 1 bits into 0 bits. This means that all of the values that Set B represents are now 0 bits. When we AND these 0 bits with the 1 bits of Set A, the result is a 0 bit. This subtracts out the Set B values from Set A.

Finally, we knock Subgoal #3 out of the park because by inverting Set B, we take all of the values it doesn’t have and flip them into 1 bits. When we AND these 1 bits with Set A’s 1 bits, the result will be a 1 bit.

And so, the pithy line A & ~B cleverly produces the difference between Set A and Set B. Just wow.