Verify if a binary array is a subset of another one in C

Question

I need to verify if the bits in an array of bytes (i.e. chars) are a subset of another array of the same type: for example, 0001.0011 (19) is a subset of 0011.0011 (51), while 0000.1011 (11) is not.

I started playing with bitwise operations, and almost solved it with a XOR/OR/XOR sequence:

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;
}

but it fails (always returning TRUE) if set_a is zero (0000.0000). I tried different strategies (such as Bloom filters), but probably due to my programming skills it was far from fast or at least elegant.

Is there any standard, elegant way of doing this without exceptions?

EDIT: to be clear, in this context "subset" means that all bits TRUE in the first array (set_a) are also TRUE in the second one (set_b). There might be other bits TRUE in the second array, but it does not matter if they are FALSE in first array.

Perhaps I'm missing something in the question, but what is your definition of a subset in this context? — Corbin
– Corbin, Commented Dec 26, 2011 at 22:09
If your definition of a subset is what you appear to think it is, (judging by your code,) then you should not be bothering us with arrays, and you could just be asking us how to figure out whether the '1' bits of an int are a subset of the '1' bits of another int. — Mike Nakis
– Mike Nakis, Commented Dec 26, 2011 at 22:17
@MikeNakis that is exactly what I want, but the number of bits to verify is not constant (ranging from ~15 to ~100). I though about using two long integers, but it was more difficult than using an array of bytes... — Giacomo
– Giacomo, Commented Dec 26, 2011 at 22:24

SCGH · Accepted Answer · 2018-11-17 06:30:35Z

18

a is a subset of b if and only if (a | b) == b. If this condition is satisfied for each byte, return TRUE. Otherwise return FALSE.

Or equivalently (a & b) == a.

edited Nov 17, 2018 at 6:30

SCGH

9678 silver badges14 bronze badges

answered Dec 26, 2011 at 22:20

Eser Aygün

8,1041 gold badge22 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Daniel Fischer Over a year ago

Alternatively: if and only if a & b == a.

swami Over a year ago

great answer... anybody know how to modify this so that it is a strict subset (i.e. equality returns false)?

Mike Nakis · Accepted Answer · 2011-12-26 22:40:16Z

5

I am not sure it is correct to say that your code fails just because it returns TRUE if set_a is an array of zeros, because from a purely theoretical mathematical point of view, the empty set is a subset of any other set. If you do not like that, then you should just add an extra check to see if set_a is an array of zeros, and if so, return FALSE right away.

answered Dec 26, 2011 at 22:40

Mike Nakis

63k11 gold badges128 silver badges173 bronze badges

Comments

hugomg · Accepted Answer · 2011-12-26 22:14:07Z

5

a is a subset of b is every bit in a implies the corresponding bit in b

a -> b

or equivalently,

~a | b //not a or b

should give 1111111.

Testing the negation agains zero might be simpler though (checking if there are no cases where we have a bit set in a but not in 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;
}

I don't remember if the bitwise stuff works properly with chars or if you need to cast to unsigned first.

answered Dec 26, 2011 at 22:14

hugomg

70.4k30 gold badges168 silver badges257 bronze badges

3 Comments

Giacomo Over a year ago

Much better than my code, but it still returing me TRUE if set_a is an array os zeros... Perhaps I messed up somewhere else?

Carey Gregory Over a year ago

Giacomo is right: your solution will always return true if set_a is zero.

Carey Gregory Over a year ago

@Giacomo: However, by your definition it's unclear whether missingno's solution is correct or not. By a very strict reading of your definition, his solution is correct.

EthOmus · Accepted Answer · 2012-06-17 04:47:26Z

0

A technical trivia , adding "(theSubsetUnderTest) &&" to the left of your expression should exclude the special case of 0.

edited Jun 17, 2012 at 4:47

answered Jun 17, 2012 at 4:33

EthOmus

592 silver badges6 bronze badges

Collectives™ on Stack Overflow

Verify if a binary array is a subset of another one in C

4 Answers 4

2 Comments

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related