Representing a set of integers with bits in C

Question

I got tasked to make a typedef which will represent an array of numbers from 0 to 127.

The numbers cannot repeat - it's a set of integers.

This is not good because it consumes too much data:

typedef struct set {
    char array[128];
} some_set;

as for later this data structure will be used to define different sets (set_a, set_b, set_c, etc.) which will be used for different operations like:

• print_set which will print the set
• union_set which combines 2 sets into a 3rd set
• intersect_set which will intersect 2 sets and save the data in the 3rd

Someone suggested to represent each number with a bit, but I can't really wrap my head around it.

Answer 1

You cannot do this just with a typedef.

Given that, any type which contains at least 128 bits will be enough to implement this. Examples:

typedef uint32_t intset[4]; // array
typedef struct {uint64_t data[2];} intset; // struct containing an array
typedef uint128_t intset; // built-in 128-bit integer type

In addition to the typedef, you have to define functions that work with the data structure. For example:

void intset_init(intset *set);
void intset_add(intset *set, int n);
void intset_remove(intset *set, int n);
bool intset_check(intset *set, int n);
bool intset_is_empty(intset *set);

Each such function should use bit-fiddling to do its work. For example:

typedef uint32_t intset[4];

void intset_add(intset *set, int n)
{
    (*set)[n / 32] |= (uint32_t)1 << (n % 32);
}

---

It may be more efficient to pass and return the data structure by value, not by pointer. If you want this, you cannot use an array typedef - use any other one which is convenient.

typedef struct {uint64_t data[2];} intset;

intset intset_add(intset set, int n)
{
    set.data[n / 64] |= (uint64_t)1 << (n % 64);
    return set;
}