C语言中用位表示整数集合：typedef实现及操作疑问

嘿，我来把位集合的思路掰碎了讲清楚，顺便给你写好核心操作的代码示例，解决你空间占用大的问题！

为什么位表示更省空间？ #

你现在用的char array[128]结构体，每个元素占1字节（8位），总共要128字节才能存0-127的存在标记。但其实我们只需要1位就能标记一个数是否在集合里——1表示存在，0表示不存在。128个数刚好需要128位，也就是16字节（128/8），空间直接缩小到原来的1/8，后续定义set_a、set_b这类集合时能省不少内存。

位集合的核心原理 #

把0-127每个整数对应到一个二进制位的位置：

• 数字0 → 第0位
• 数字1 → 第1位
• ...
• 数字127 → 第127位

我们可以用两个uint64_t（每个64位，刚好凑够128位）来存储这些位，位操作会更高效：

#include <stdint.h>
// 用两个64位无符号整数存128位，对应0-127的数
typedef uint64_t some_set[2];

基础位操作函数（添加、判断存在、删除） #

先写几个辅助函数帮你操作单个元素：

// 向集合中添加数字n（n必须在0-127之间）
void add_to_set(some_set set, int n) {
    int idx = n / 64; // 确定是第一个还是第二个uint64_t
    int bit_pos = n % 64; // 确定在该uint64_t中的位位置
    set[idx] |= (1ULL << bit_pos); // 把对应位设为1
}

// 判断数字n是否在集合中
int is_in_set(some_set set, int n) {
    int idx = n / 64;
    int bit_pos = n % 64;
    return (set[idx] & (1ULL << bit_pos)) != 0;
}

// 从集合中删除数字n
void remove_from_set(some_set set, int n) {
    int idx = n / 64;
    int bit_pos = n % 64;
    set[idx] &= ~(1ULL << bit_pos); // 把对应位设为0
}

实现你需要的集合操作 #

接下来就是你要的print_set、union_set、intersect_set：

1. 打印集合 #

遍历0-127，把存在的数字打印出来：

#include <stdio.h>

void print_set(some_set set) {
    printf("{ ");
    int first = 1;
    for (int i = 0; i <= 127; i++) {
        if (is_in_set(set, i)) {
            if (!first) {
                printf(", ");
            }
            printf("%d", i);
            first = 0;
        }
    }
    printf(" }\n");
}

2. 求两个集合的并集 #

并集的规则是：只要其中一个集合有该数字，结果集合就包含它。对应位操作就是按位或（|）：

void union_set(some_set result, some_set a, some_set b) {
    result[0] = a[0] | b[0];
    result[1] = a[1] | b[1];
}

3. 求两个集合的交集 #

交集的规则是：只有两个集合都有的数字，结果集合才包含它。对应位操作就是按位与（&）：

void intersect_set(some_set result, some_set a, some_set b) {
    result[0] = a[0] & b[0];
    result[1] = a[1] & b[1];
}

测试示例 #

给你一个简单的测试代码，看看怎么用这些函数：

int main() {
    some_set set_a = {0}; // 初始化集合为空
    some_set set_b = {0};
    some_set set_union, set_intersect;

    // 给set_a添加元素
    add_to_set(set_a, 5);
    add_to_set(set_a, 10);
    add_to_set(set_a, 127);

    // 给set_b添加元素
    add_to_set(set_b, 10);
    add_to_set(set_b, 20);
    add_to_set(set_b, 127);

    // 打印原集合
    printf("set_a: ");
    print_set(set_a);
    printf("set_b: ");
    print_set(set_b);

    // 计算并集和交集
    union_set(set_union, set_a, set_b);
    intersect_set(set_intersect, set_a, set_b);

    printf("Union: ");
    print_set(set_union);
    printf("Intersect: ");
    print_set(set_intersect);

    return 0;
}

运行这段代码，输出会是：

set_a: { 5, 10, 127 }
set_b: { 10, 20, 127 }
Union: { 5, 10, 20, 127 }
Intersect: { 10, 127 }

是不是比原来的char数组方案高效多了？如果还有疑问随时问！

内容的提问来源于stack exchange，提问作者Milo