Проверьте, является ли двоичный массив подмножеством другого в 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;
}

, но это не удается (всегда возвращает TRUE), если set_a ноль (0000.0000).Я пробовал разные стратегии (например, фильтры Блума), но, вероятно, из-за моих навыков программирования это было далеко не быстро или хотя бы элегантно.

Есть ли какой-нибудь стандартный, элегантный способ сделать это без исключений?

РЕДАКТИРОВАТЬ: для ясности, в этом контексте «подмножество» означает, что все биты ИСТИНА в первом массиве (set_a) также ИСТИНА во втором (set_b).Во втором массиве могут быть другие биты TRUE, но не имеет значения, являются ли они FALSE в первом массиве.

Answer 1

a является подмножеством b тогда и только тогда, когда (a | b) == b.Если это условие выполняется для каждого байта, вернуть TRUE.В противном случае вернуть FALSE.

или эквивалентно (a & b) == a.

Answer 2

Я не уверен, что правильно сказать, что ваш код терпит неудачу только потому, что он возвращает TRUE, если set_a является массивом нулей, потому что с чисто теоретической математической точки зрения пустой набор является подмножество любого другого набора. Если вам это не нравится, тогда вам нужно просто добавить дополнительную проверку, чтобы увидеть, является ли set_a массивом нулей, и если да, сразу вернуть FALSE.

Answer 3

a - это подмножество b, каждый бит в a подразумевает соответствующий бит в b

a -> b

или эквивалентно,

~a | b //not a or b

следуетgive 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;
}

Я не помню, правильно ли работает битовая вещь с символами или нужно ли сначала приводить к unsigned.

Answer 4

Техническая мелочь, добавление "(theSubsetUnderTest) &&" слева от вашего выражения должно исключить особый случай 0.