Представление набора целых чисел с битами в C

Question

Мне нужна помощь.Мне поручили сделать typedef, который будет представлять массив чисел от 0 до 127. Числа не могут повторяться - это набор целых чисел.

Это не хорошо, потому что он потребляет слишком много данных:

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

, поскольку в дальнейшем эта структура данных будет использоваться для определения другого набора (set_a, set_b, set_c и т. Д.), Который будет использоваться для различных операций, таких как:

      print_set which will print the set  

      union_set which combines 2 sets into 3rd set

      intersect_set which will intersect 2 sets and save the data in the 3rd

thisпримеры использования.

Кто-то предложил представлять каждое число с небольшим количеством, но я не могу действительно обернуть его вокруг.

Answer 1

Вы не можете сделать это только с typedef.

Учитывая, что для реализации этого будет достаточно любого типа, который содержит не менее 128 бит.Примеры:

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

В дополнение к typedef необходимо определить функции, которые работают со структурой данных.Например:

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

Каждая такая функция должна использовать bit-fiddling для своей работы.Например:

typedef uint32_t intset[4];

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

---

Может быть более эффективно передавать и возвращать структуру данных по значению, а не по указателю.Если вы хотите этого, вы не можете использовать массив typedef - используйте любой другой, который удобен.

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