有没有一种算法可以找到 2 个给定可能的二进制数的并集和交集

Question

给定两个 N 位二进制数（例如我将使用 5）

1. XXX0X 这意味着 1) 具有第 2 位为 0 的所有二进制数组合，因此总共有 16 种组合（ X 既是 0 又是 1）
2. XXXX0 相反，这个是第 1 位为 0 的二进制数的所有二进制组合，所以这里也是 16 个组合。

现在的问题是这 2 个共享一些组合，所以如果我想从所有 32 个可能的数字中取出可以用 5 位写入的数字，我只会做这 2 个组合中的一部分：

1. 并集 2)= 1) + 2) - 1) 交集 2) = 16+16-8= 24 种组合

是否有任何算法可以执行此并集和交集，而不需要执行创建所有可能的组合然后检查女巫组合是否相等之类的操作？

我想到了最简单的事情，用 N 位创建所有 2^n 可能的二进制数，然后面对字符串来检查交集，但我想应该有一种更快的方法来做到这一点。 如果这是一个已知问题或类似的问题，我什至不知道要搜索什么，所以如果它已经存在或已知，我很抱歉。

Answer 1

检查设置位 (=1) 比检查零更容易。如果您需要零，您可以随时否定 (

~

) 您的模式。

现在，如果您有两个测试模式：

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

你可以

or

他们在一起

mask = test1 | test2

然后，对于每个数字

i

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

完整代码：

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'))))