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

Question

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

Answer 1

用与&预算检测.
#include
//检测定义成一个宏
#defineIS_SET(ch,idx)((ch)&(0x01<<(idx)))
intmain()
{
unsignedcharch=0x14;//二进制00010100;
//从右往左,第三位(下标从0开始,所以程序里是2)是1吗?
if(IS_SET(ch,2)){
printf("YES\n");
}else{
printf("NO\n");
}
return0;
}
                            

Answer 2

要节省空间的话可以使用位操作来完成，位操作的效率其实挺高的，并没有你想象的那么低，像楼上的把位操作定义成宏直接用也会被做成函数效率高。
下面是使用位操作实现的一个数组和测试，可以改造成一个队列：
C#include
//机器字长，一般C/C++规定int类型为机器字长
//选择和机器字长一致的变量可以加快访问运算速度
#defineCPU_SIZEsizeof(unsignedint)
//一机器字长能够保存的比特数
#defineCPU_SIZE_BIT(CPU_SIZE*8)
//计算_bitlen需要都少个机器字长
#defineLEN_OF_BITS(_bitlen)((_bitlen+CPU_SIZE_BIT-1)/CPU_SIZE_BIT)
//定义_var为_bitlen比特变量
//在C89上，定义需要放在函数开始位置
#defineDEFINE_BITS(_var,_bitlen)unsignedint_var[LEN_OF_BITS(_bitlen)]
//将_var的第_ix置1
#defineBIT_SET(_var,_ix)(_var)[(_ix)/CPU_SIZE_BIT]|=(1<<((_ix)%CPU_SIZE_BIT))
//将_var的第_ix置0
#defineBIT_RESET(_var,_ix)(_var)[(_ix)/CPU_SIZE_BIT]&=~(1<<((_ix)%CPU_SIZE_BIT))
//获取_var的第_ix位
#defineBIT_GET(_var,_ix)(((_var)[(_ix)/CPU_SIZE_BIT]>>((_ix)%CPU_SIZE_BIT))&0x01)
//测试用的比特数目
#defineBITLEN100
intmain()
{
DEFINE_BITS(bits,BITLEN);//定义bits为BITLEN个位的变量
inti;
//输出一下这些bits到底占多少字节
printf("sizeof(bits)=%d\n",sizeof(bits));
//设置
for(i=0;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;iprintf("%02d:%d",i,BIT_GET(bits,i));
if(i%10==9){
printf("\n");
}
}
return0;
}
代码很多常量运算会在编译阶段自动优化，所以不必刻意担心。
测试输出：
E:\TEMP>gcct.c-ot.exe&&t.exe
sizeof(bits)=16
00:101:002:003:104:005:106:107:008:009:1
10:111:012:113:014:015:116:017:018:119:0
20:121:122:023:024:125:126:027:128:029:0
30:131:032:033:134:035:136:137:038:039:1
40:141:042:143:044:045:146:047:048:149:0
50:151:152:053:054:155:156:057:158:059:0
60:161:062:063:164:065:166:167:068:069:1
70:171:072:173:074:075:176:077:078:179:0
80:181:182:083:084:185:186:087:188:089:0
90:191:092:093:194:095:196:197:098:099:1
可以看到100位数据的保存只用了16个字节。
如你所见，代码的可读性变差很多，有的时候需要考虑这种牺牲是否是值得的
时间和空间两者之间本身就是矛盾的，只能根据具体的情况来进行二者之间的权衡。unsignedchar的话空间的确不够么？位操作的话效率的确跟不上来了么？