0

I am trying to implement boolean data type in C. Basically, I am working with sets.

The following code can be used to access each bit but I am unsure whether I can represent sets using this method. Can somebody clarify this for me?

struct SET {
unsigned int b0     :1;     // bit 0 single bit
unsigned int b1     :1;     // bit 1 single bit
unsigned int b2     :1;
 unsigned int b3    :1;
 };

I can define two structures s1 and s2.. and I will be able to access each bit of these structures (treated as boolean strings).

I will have to perform set operations like UNION, INTERSECTION and MEMBERSHIP. Is this even possible in C?

Note: I cannot use Java, only C.

  • What kind of sets do you need? Do you mean bitsets where each bit represents if something is included in the set? – Bart van Ingen Schenau Aug 5 '14 at 12:53
  • @BartvanIngenSchenau thats exacyly what I mean.. my sets look like this set A={p,q,r} and set B={q,r} union,intersection,membership,complement,subset are the operations that I want to be able to perform – GermanShepherd Aug 5 '14 at 13:02
  • Are you wedded to bitfields or are you open to other implementations? – Blrfl Aug 5 '14 at 13:03
  • @andy256: thanks for the encouragement..but it seems like java is a friendlier language for Boolean operations..in my opinion, but my mentor and guide wants it all in C..!! I would appreciate it if, you gave me a solution – GermanShepherd Aug 5 '14 at 13:05
  • 2
    There are heaps of implementations online. Let your fingers do the Googling. Clearly you have not done the research. And from what you say, you're a student, and should be doing your work yourself. – andy256 Aug 5 '14 at 13:11
1

C doesn't have any built-in set operations, but if your sets can be represented by a bitset with fewer than 64 bits (32 in older implementations), then you can use bit-operations to simulate the set operations (using AND (&) for set intersection and OR (|) for set union).

Your structure is easy for testing membership (just see if the corresponding member is not 0), but not that easy for operations on multiple bits. That is easier on an unsigned number. To get the best of both worlds, use a union:

union SET {
  struct items {
    unsigned int a: 1;
    unsigned int b: 1;
    unsigned int c: 1;
    unsigned int d: 1;
    unsigned int e: 1;
    unsigned int f: 1;
    unsigned int g: 1;
    unsigned int h: 1;
  };
  uint8_t bits; // As we only have 8 items for our set
};

You do the bit operations on the bits member, and the membership tests/sets on the items.[abcdefgh] members.

| improve this answer | |
  • the problem with your approach is that, I cannot set the bit field to 0.. I get an error..! – GermanShepherd Aug 5 '14 at 17:03
  • @user59288: What error do you get? To access/modify all (or multiple) bits, you need to use the bits member. Through items, you can only work with individual bits. – Bart van Ingen Schenau Aug 5 '14 at 18:08
  • the error was: cannot set the bit field to zero.. – GermanShepherd Aug 6 '14 at 1:12
0

In memory these can be accessed as flags, so you can use standard flag operations,

struct SET {
 unsigned int b0     :1;     // bit 0 single bit
 unsigned int b1     :1;     // bit 1 single bit
 unsigned int b2     :1;
 unsigned int b3     :1;
};

struct SETFlag {
    union {
        SET set;
        unsigned int set_as_flag;
    };
};


 /* example use */
 SETFlag a, b, c;
 /* initialize */
 c.set_as_flag = a.set_as_flag | b.set_as_flag;  /* union */
 /* c.set, now you can use set */

This assumes you have <= 32 members for a 4 byte int, you could ensure its value is correct,

_Static_assert(sizeof(((struct SETFlag *)0)->set) <=
               sizeof(((struct SETFlag *)0)->set_as_flag),
               "SETFlag.set_as_flag is too small!");

However all this begs the question, why not just use flags.

| improve this answer | |
  • the problem that I have is commonly called "the state explosion problem" and because I am using a graph kind of data structure elsewhere in my program, it becomes difficult for me to keep track of so many flags.. – GermanShepherd Aug 5 '14 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.