CODEWITHSUNDEEP
cdata-structuressetbitwise-operators
Milo
Milo

Reputation: 141

Representing a set of integers with bits in C

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:

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

Upvotes: 2

Views: 273

Answers (1)

anatolyg
anatolyg

Reputation: 28279

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

Upvotes: 2

Related Questions