c - 验证二进制数组是否是 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 过滤器)，但可能由于我的编程技能，它远谈不上快速或至少不够优雅。

是否有任何标准、优雅的方式来无一异常(exception)地做到这一点？

编辑:明确地说，在此上下文中，“子集”意味着第一个数组 (set_a) 中的所有位 TRUE 在第二个数组 (set_b) 中也为 TRUE。第二个数组中可能有其他位为 TRUE，但它们在第一个数组中是否为 FALSE 并不重要。

Answer 1

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

或者等效于 (a & b) == a。