C语言中如何最节省地保存0,1的一个长队列？

Question

现在暂时我用unsigned char类型来替代bool,因为C语言没有bool嘛。
如果只是保存的话可以每八位变成一个char去储存，但问题是我需要快速访问那些位是0还是1

Answer 1

用与&预算检测.

#include <stdio.h>

// 检测定义成一个宏
#define IS_SET(ch, idx) ((ch) & (0x01<<(idx)))

int main()
{
    unsigned char ch = 0x14; // 二进制 0001 0100;
    // 从右往左, 第三位(下标从0开始, 所以程序里是2)是1吗?
    if (IS_SET(ch, 2)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}

Answer 2

要节省空间的话可以使用位操作来完成，位操作的效率其实挺高的，并没有你想象的那么低，像楼上的把位操作定义成宏直接用也会被做成函数效率高。

下面是使用位操作实现的一个数组和测试，可以改造成一个队列：

C
#include <stdio.h>


// 机器字长，一般C/C++规定int类型为机器字长
// 选择和机器字长一致的变量可以加快访问运算速度
#define CPU_SIZE    sizeof(unsigned int)

// 一机器字长能够保存的比特数
#define CPU_SIZE_BIT    (CPU_SIZE*8)

// 计算_bitlen需要都少个机器字长
#define LEN_OF_BITS(_bitlen)    ((_bitlen+CPU_SIZE_BIT-1)/CPU_SIZE_BIT)

// 定义_var为_bitlen比特变量
// 在C89上，定义需要放在函数开始位置
#define DEFINE_BITS(_var, _bitlen)  unsigned int _var[LEN_OF_BITS(_bitlen)]

// 将_var的第_ix置1
#define BIT_SET(_var, _ix) (_var)[(_ix)/CPU_SIZE_BIT] |= (1<<((_ix)%CPU_SIZE_BIT))

// 将_var的第_ix置0
#define BIT_RESET(_var, _ix) (_var)[(_ix)/CPU_SIZE_BIT] &= ~(1<<((_ix)%CPU_SIZE_BIT))

// 获取_var的第_ix位
#define BIT_GET(_var, _ix)  (((_var)[(_ix)/CPU_SIZE_BIT]>>((_ix)%CPU_SIZE_BIT))&0x01)


// 测试用的比特数目
#define BITLEN  100

int main()
{
    DEFINE_BITS(bits, BITLEN);  // 定义bits为BITLEN个位的变量
    int i;

    // 输出一下这些bits到底占多少字节
    printf("sizeof(bits)=%d\n", sizeof(bits));

    // 设置
    for(i=0; i<BITLEN; ++i){
        // 只是做个简单的测试：将3和5倍数位置上的位置位1
        // 其他置0
        if(i%3==0 || i%5==0){
            // 第i个置为1
            BIT_SET(bits, i);
        }
        else{
            // 第i个置为0
            BIT_RESET(bits, i);
        }
    }

    // 输出
    for(i=0; i<BITLEN; ++i){
        printf("%02d:%d ", i, BIT_GET(bits, i));
        if(i%10==9){
            printf("\n");
        }
    }
    return 0;
}

代码很多常量运算会在编译阶段自动优化，所以不必刻意担心。

测试输出：

E:\TEMP>gcc t.c -o t.exe && t.exe
sizeof(bits)=16
00:1 01:0 02:0 03:1 04:0 05:1 06:1 07:0 08:0 09:1
10:1 11:0 12:1 13:0 14:0 15:1 16:0 17:0 18:1 19:0
20:1 21:1 22:0 23:0 24:1 25:1 26:0 27:1 28:0 29:0
30:1 31:0 32:0 33:1 34:0 35:1 36:1 37:0 38:0 39:1
40:1 41:0 42:1 43:0 44:0 45:1 46:0 47:0 48:1 49:0
50:1 51:1 52:0 53:0 54:1 55:1 56:0 57:1 58:0 59:0
60:1 61:0 62:0 63:1 64:0 65:1 66:1 67:0 68:0 69:1
70:1 71:0 72:1 73:0 74:0 75:1 76:0 77:0 78:1 79:0
80:1 81:1 82:0 83:0 84:1 85:1 86:0 87:1 88:0 89:0
90:1 91:0 92:0 93:1 94:0 95:1 96:1 97:0 98:0 99:1

可以看到100位数据的保存只用了16个字节。
如你所见，代码的可读性变差很多，有的时候需要考虑这种牺牲是否是值得的

时间和空间两者之间本身就是矛盾的，只能根据具体的情况来进行二者之间的权衡。unsigned char的话空间的确不够么？位操作的话效率的确跟不上来了么？

Answer 3

用bit来存， 一个Byte能存8个bit，而bit有只有0,1两种表示。判断是0还是1用位运算。

Answer 4

纯C么，C++有bitset类可以用

Answer 5

可以参考《编程珠肌》开头处理连续电话号码那里例子： 使用到bitset

Answer 6

看了下回答，基本都是bitset的思路，我开下脑洞给个不同的。

原题说到队列，所以我猜测也有可能是，已经有个队列，需要在每个节点里加入一个bool字段。这种情况，可以利用内存对齐时浪费的地址低位来存储一些信息。

直接写个简单例子：

#include <stdio.h>
#include <stdint.h>

typedef struct node {
    union {
        unsigned char is_true:1; //This will only work on little endian platforms
        struct node* next;
    };
    /* Other stuff */
}node_t;

int main()
{
    node_t a, b, c;

    //Create a list
    c.next = NULL;
    b.next = &c;
    a.next = &b;

    //Set the bool flag
    b.is_true = 1;

    node_t* itr = &a;

    //Check the bool flag
    while(itr)
    {
        if (itr->is_true) {
            /* Do something */
        }
        itr = (node_t*)((uintptr_t)itr->next ^ itr->is_true);
    }

    return 0;
}

如果觉得影响了next指针的使用方式不舒服，那可以不使用union。不过这样的话，虽然指定了只用1位，实际还是会至少分配一字节。

不管了，看到问题忍不住引申一下。我其实是更倾向于bitset的。

Answer 7

位域操作不是更直接吗?

Answer 8

只是为了省空间使用位图是不错的选择。