Проверьте, является ли двоичный массив подмножеством другого в 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). Я пробовал разные стратегии (например, фильтры Bloom), но, вероятно, из-за моих навыков программирования он был далек от быстрого или, по крайней мере, элегантного.

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

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

Answer 1

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

Answer 2

a является подмножеством b каждый бит в a означает соответствующий бит в b

a -> b 

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

~a | b //not a or b 

должен дать 1111111.

Тестирование Отрицание Agains ноль может быть проще, хотя (проверка, если нет ни одного случая, когда мы имеем бит, установленный в но не б)

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 3

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

Answer 4

технический пустяки, добавив «(theSubsetUnderTest) & &» в левой части выражения следует исключить частный случай 0.