在 C 中用位表示一组整数

Question

我的任务是制作一个 typedef，它将表示从 0 到 127 的数字数组。

数字不能重复 - 它是一组整数。

这不好，因为它消耗了太多数据：

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

至于稍后这个数据结构将用于定义不同的集合（set_a、set_b、set_c 等），这些集合将用于不同的操作，例如：

print_set 将打印集合
union_set 将 2 组合并为第 3 组
intersect_set这将与2组相交并将数据保存在第3组

有人建议用一个位来表示每个数字，但我实在想不通。

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

按值而不是指针传递和 return 数据结构可能更有效。如果你想要这个，你不能使用数组 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;
}

在 C 中用位表示一组整数

Representing a set of integers with bits in C

c

set

bitwise-operators

data-structures