A logical operator representing the intersection of two sets?

Answer 1

There is no built-in logical operator that can achieve this. Logical operators operate upon Boolean operands (true and false) and output a Boolean value. Converting a set to a Boolean value won't tell us which individual elements exist within that set and without that vital information we cannot represent the intersection of two such sets.

To represent the intersection of two sets we need to represent the "universe of elements" as a bitmap, where each bit represents exactly one element of the universe. If the universe has 10 elements then we need a bitmap of 10 bits:

1111111111 = universe of elements

Note that a bitmap is nothing more than a binary value.

We can then represent the sets, A and B, as subsets of this universe:

A = 1011011011

B = 0101101101

If we perform a logical AND (operator &&) these binary values would implicitly convert to Boolean values. Given that both values are non-zero, they will both convert to true and the result would also be true:

C = A && B; // e.g., C = true && true = true

This would only tell us that an intersection exists, it will not tell us what the intersection actually is.

However, if we perform a bitwise AND (as opposed to a logical AND), we can determine which individual bits are present in both sets:

C = A & B; // e.g., C = 1011011011 & 0101101101 = 0001001001

Here we can see that both sets contain the 1st, 4th and 7th elements of the universe (starting from the low-order bit, reading right-to-left).

The built-in logical AND operator can only accommodate as many bits as will fit in a word. If the machine supports 64-bit operations, then the universe of elements is limited to 64 elements at most. If we have a larger universe, we cannot use built-in operators and must provide a named function instead. First, let's define a variable length set of integers as an array:

struct set {

int* data; // pointer to an array of integers

size_t size; // length of the array

};

Now we can define an intersect function:

set intersect (set A, set B) {

set C;

C.size = A.size>B.size?A.size:B.size; // use the larger of the two set sizes

C.data = malloc (C.size * sizeof (int)); // allocate memory

C.size=0; // start at index 0

for (int i=0; i<A.size, ++i) {

for (int j=0; j<B.size, ++j) {

if (A.data[i] == B.data[j]) C.data[C.size++] = A.data[i];

}

}

C.data = realloc (C.size * sizeof(int)); // shrink the array (remove unused elements)

return C;

}

This is clearly less efficient than using the built-in operator &. However, we can possibly improve the efficiency by converting the sets to bitmaps and dividing those bitmaps into groups of bits that the built-in operator can accommodate efficiently (such as 32-bit groupings), however the conversion processes also have to be taken into account to determine whether the overall efficiency is improved. This is left as an exercise for the reader.

Answer 2

The bitwise AND operator (symbolised with '&' in C, C++ and Java).