使用不在乎位哈希二进制数

Question

我怎样才能知道一个二进制数是否包含在一个集合中，其中集合的元素可能没有关心位？我想过使用哈希表，但有必要在哈希表中使用不在乎位复制数字，以涵盖所有可能性。

例如：这组数字是：

   0  00x1
   1  10xx
   2  110x
   3  1010
   4  11x1
   5  0010

数字为 0011，结果应为 0。

Answer 1

如果二进制数的位数有限，那么您可以复制那些不在乎的位并将二进制数转换为整数，然后将这些整数用作映射的键和其他值。例

0 00x1

1 10xx

可以转换为

0001 0

0011 0

1000 1

1001

年1

1010 1

1011 1

并另存为

我·

1 0

3 0

8 1

9 1

10 1

11 1

其中 i 是键，j 是值

Answer 2

假设你有二进制数 1xxx，它将匹配 8 个数字。因此，不要为每个选项进行复制。

你必须把"不在乎"的部分保留在某个地方。为此使用另一个数字，将"不在乎"位设置为 1。如果我们回顾一下您的示例：

i  x       y
0  00x1    0010
1  10xx    0011
2  110x    0001
3  1010    0000
4  11x1    0010
5  0010    0000

你需要决定对 x、0 或 1 使用什么。您可以使用其中任何一个，一旦您将信息保留在第二个数字中，就没关系了。

现在使用按位运算：

if ((n ^ x[i]) | y[i]) == y[i] then match

此解决方案基于检查是否存在任何不匹配位（不关心位除外）。（n xor x[i]） 给出不匹配的位，然后用 y[i] 或它不应该与 y[i] 不同。

如果我们回顾您的示例，并假设您选择 0 作为 x，则检查变为

i:0 -->> ((0011 ^ 0001) | 0010) == 0010  -->> match!
i:1 -->> ((0011 ^ 1000) | 0011) != 0011  -->> no match!
i:2 -->> ((0011 ^ 1100) | 0001) != 0001  -->> no match!
i:3 -->> ((0011 ^ 1010) | 0000) != 0001  -->> no match!
i:4 -->> ((0011 ^ 1101) | 0010) != 0001  -->> no match!
i:5 -->> ((0011 ^ 0010) | 0000) != 0000  -->> no match!