Search code examples
algorithmset-theory

Finding a Set based on Bit Occurence


I am trying to find a column of bits that appears more than once. Let me present you with an example:

       X Y Z   
Set A  0 1 0
Set B  0 0 1
Set C  0 1 0
Set D  0 0 0

Through a UNION operation, I am able to know which COLUMN from the list of sets has its bit set to 1. If I do A UNION B UNION C UNION D then we get 0 1 1, which means Column X has no bits set to 1 and Columns Y and Z has AT LEAST 1 of the bits set to 1.

My problem is I'm trying to find the right set operation to find columns that has bits set to 1 more than once. With the above given example, Column Y has 2 bits set to 1. Thus the result should be 0 1 0.

I tried doing intersections which is the most logical thing to do but produces a different result.

I appreciate is someone could guide me what combination of set operations should I perform to get the desired result. Thanks in advance.


Solution

  • My problem is I'm trying to find the right set operation to find columns that has bits set to 1 more than once.

    Here's one way:

    (A ∩ B) ∪ (A ∩ C) ∪ (A ∩ D) ∪ (B ∩ C) ∪ (B ∩ D) ∪ (C ∩ D)

    That said, math is pretty flexible; you can literally just say "the set containing all elements that appear in at least two of the sets A, B, C, D", and mathematicians will accept that for most purposes.