验证二进制数组是否是C中另一个数组的子集

Question

我需要验证字节数组（即，字符）中的位是否是相同类型的另一个数组的子集：例如，0001.0011（19）是0011.0011（51）的子集，而0000.1011（11）不是。

我开始玩按位运算，几乎用XOR / OR / XOR序列解决了它：

int is_subset (char *set_a, char *set_b, int size)
{
  /* The operation is performed with three bitwise operations, resulting in a
   * sequence of bits that will be equal to zero if set_a is a subset of
   * set_b. As a bonus, the positions where the sets differ will be
   * available in the resulting sequence, and thus the number of differing
   * positions can be obtained by counting the number of bits set (for exemple,
   * with __builtin_popcount in GCC).
   *
   *   Exemple (TRUE):              Exemple (FALSE):
   *   ================             ================
   *   set_a   00010011             set_a   00001011
   *   set_b   00110011             set_b   00110011
   *   ----------------             ----------------
   *   XOR     00100000             XOR     00111000
   *   set_b   00110011             set_b   00110011
   *   ----------------             ----------------
   *   OR      00110011             OR      00111011
   *   set_b   00110011             set_b   00110011
   *   ----------------             ----------------
   *   XOR     00000000             XOR     00001000
   */

  int i;
  for (i = 0; i < size; i++)
    if ( (((set_a[i] ^ set_b[i]) | set_b[i]) ^ set_b[i]) != 0)
      return FALSE;

  return TRUE;
}

但如果set_a为零（0000.0000），则会失败（始终返回TRUE ）。我尝试了不同的策略（例如Bloom过滤器），但是可能由于我的编程技能，它远远不够快速，或者至少不够优雅。

有没有任何标准，优雅的方法来做到这一点？

编辑：要清楚，在此上下文中，“子集”表示第一个数组（set_a）中的所有位TRUE也在第二个数组（set_b）中为TRUE。在第二个数组中可能还有其他位TRUE，但是在第一个数组中它们是否为FALSE并不重要。

Answer 1

a是b每个位中的子集a意味着中的相应位b

a -> b

或等效地，

~a | b //not a or b

应该给1111111。

尽管如此，再次测试否定可能更简单（检查是否没有我们在 a 中设置了位但在 b 中没有设置的情况）

0 == ( a & ~b)

int is_subset (char *set_a, char *set_b, int size)
{
  int i;
  for (i = 0; i < size; i++){
    if(0 != (set_a[i] & (~ set_b[i])))
      return FALSE;
  }
  return TRUE;
}

我不记得按位的东西是否与字符一起正常工作，或者您是否需要先转换为无符号。

Answer 2

a是bif和only if 的子集(a | b) == b。如果每个字节都满足此条件，则返回TRUE。否则返回FALSE。

或等效地(a & b) == a。

Answer 3

如果 set_a 是一个零数组，我不确定说你的代码失败只是因为它返回 TRUE 是否正确，因为从纯理论数学的角度来看，空集是任何其他集的子集。如果您不喜欢那样，那么您应该添加一个额外的检查以查看 set_a 是否是一个零数组，如果是，则立即返回 FALSE。