Is there an algorithm to find the union and intersection of 2 given possible binary numbers

Question

Given two binary numbers with N bits (for the example I'll use 5)

1. XXX0X This means that 1) has all combinations of binary numbers where the 2nd bit is 0, so a total of 16 combinations ( X is both 0 and 1)
2. XXXX0 This one instead is all the binary combinations of binary numbers where the 1st bit is 0, so here too 16 combinations.

Now the issue is that those 2 share some combinations, so if i wanna take out from all 32 possible numbers that can be written with 5 bits, only the numbers that are part of those 2 combinations i will do:

1. Union 2)= 1) + 2) - 1) Intersecate 2) = 16+16-8= 24 combinations

Is there any algorithm to do this union and intersection without doing something like creating all possible combinations and then check witch ones are equal?

I thought about the simpliest thing of creating all 2^n possible binary numbers with N bits and then confronting strings to check for the intersection but i guess there should be a faster way of doing it. I didn't even know what to search if it was a known problem or something like that, so if it already exists or it's known I'm sorry.

edit:

To give more about my issue: i'm working on 3-SAT, so i have a code to solve by dpll algorithm a given problem with n variables and m clauses. when the code encounters a conflict it backtracks and gives me the reason of the conflict that's an array of k values that represents the combination of assegnation of variables that led to the conflict.

For example if i have 5 variables and the reason for the first conflict is [2,-5], i know that all combinations that have both the variable x2 as true and the variable x5 as false are out, for this example, 16 combinations are out of the possible 32.

Now if the next reason of the conflict is for example [-1,3], i know that this leaves out 16 combinations, but some are the same of the first reason, so , to know at any time how many i have already left out of the whole 2^n i have to know how many combinations the 2 reasons [2,-5][-1,3] eliminate.

i tought about creating a data structure with all 2^n combinations and every time i get the reason i pop the combinations i don't need anymore so that i won't have to check for intersections and unions.

My only issue is that i work with 100/200 variables so to create a structure with 2^200 variables seems unreasonable.

Answer 1

It's easier to check for set bits (=1) rather than zeroes. You can always negate (~) your patterns if you need zeroes.

Now, if you have two test patterns:

test1 = 0b00001 (bit 0 set)
test2 = 0b00010 (bit 1 set)

you can or them together

mask = test1 | test2

and then, for each number i

if (i & mask) is = mask  - it has bit 0 AND bit 1 set (intersection)
if (i & mask) is nonzero - it has bit 0 OR bit 1 set (union)

Full code:

test1 = 0b00001
test2 = 0b00010

mask = test1 | test2

union = []
inter = []

for (i = 0; i < 32; i++)
    if ((i & mask) === mask)
        inter.push(i)

for (i = 0; i < 32; i++)
    if ((i & mask) > 0)
        union.push(i)

console.log(String(inter.map(i => i.toString(2).padStart(5, '0'))))
console.log(String(union.map(i => i.toString(2).padStart(5, '0'))))

Answer 2

If you have a pattern for representing a set of numbers with fixed length, where for each binary digit you have

• X: the digit may be either 0 or 1
• 0: the digit must be 0
• 1: the digit must be 1
• -: the digit may be neither 0 nor 1

then you can easily compute the size of the set from the pattern in linear time:

function size(pattern) {
    return pattern.split('').map(d =>
        ({'X': 2, '0': 1, '1': 1, '-': 0}[d])
    ).reduce((prod, factor) => 
        prod * factor
    , 1);
}

Now you can run size('XXX0X') or size('XXXX0') to get 16 respectively.

And you can intersect two of these patterns to yet another pattern, using

function intersect(a, b) {
    if (a.length != b.length) throw new RangeError('Input patterns must be of same length');
    let res = '';
    for (let i=0; i<a.length; i++) {
        if (a[i] == 'X') res += b[i];
        else if (b[i] == 'X') res += a[i];
        else if (a[i] == b[i]) res += a[i];
        else res += '-';
    }
    return res;
}

so that e.g. intersect('XXX0X', 'XXXX0') returns XXX00.

However, you cannot write a union function that returns another pattern. While it may be possible for some (e.g. union(X0X, X1X) = XXX) it won't work for others, like your union(XXX0X, XXXX0) - the pattern would need to be able to represent alternation and become a regular expression. However, for regular expressions there is no linear size algorithm, it is an NP-hard problem. So yes, trying all 2ⁿ numbers against the pattern(s) is not only the simplest but also the only solution.