关于位处理及位域的思考

06 November 2013

近期事情比较多，篮球赛、志愿者，加上老师那边的工作和最近上头的看书情节，博客也有段时间没更新了。篮球赛打完了，看书的瘾也压制了一下，开始学些新东西，这不又把《C++Primer》那本大部头拿出来重新看了看。一直觉得C++是比较难学的语言，不过为了进阶还是不得不学。刚刚和师兄聊了会天，感觉找工作越来越难，突然发现要学的东西很多，而自己还在浪费时间，到现在我都不敢说自己忙了。

闲话少说，来讲讲今天的主题，关于“位”这个东西的一些感想。相信对于“位”大家一定不陌生，计算机不就是用0和1来传输信息的么，实际上，计算机说白了就是“位”处理。记得以前学习C语言，对各种类型（char，short，int等）的位宽完全没概念，觉得知道或不知道没什么区别。随着学习的深入，越来越觉得这些位宽的重要性，毕竟这些宽度决定了一个变量存储数据的容量，也是我们读写的单位。慢慢开始理解，char型啊，int型啊其实就是位宽不同，char型也可以存数字，只是大小有限（无符号型0~255等）。而char型之所以存储字符，因为字符的ASCII码就需要一个字节（8位），用别的类型比较浪费。也就是说，char不是只能存字符，int也不是只能存整数。

第一次对“位”感到神奇的是阅读《编程珠玑》的开篇那个问题，就是大数据小内存的问题。作者很巧妙的使用“位图”解决了这个难题，至今我觉得那段代码是极为神奇与优美的。不敢独享，在此给出：

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i)  {        a[i>>SHIFT] |=  (1<<(i & MASK));}
void clr(int i)  {        a[i>>SHIFT] &= ~(1<<(i & MASK));}
void test(int i) { return a[i>>SHIFT] &   (1<<(i & MASK));}

羞愧的讲，每次看到这段代码，都要想半天才能想通它的做法。

之所以想到今天的这个主题，因为最近在做的事情和它有关。大概就是从文件里面读10个bit，再处理一下变成16个比特，blahblahblah。。。那从文件里面读数据最小单位不也是一个字节么，这10个比特只能读取两个字节再移位处理。正因为此，想找个简单的办法解决这个问题，于是就搜到了下面的这个传说中的“位域”用法。

汗，之所以说是传说中，因为自己学这么久，就没听过这玩意。我们来看看这玩意到底怎么定义：

struct bitField
{
	unsigned char a:2;
	unsigned char b:3;
	unsigned char c:3;
	unsigned int  d:6;
};

bitField是位域结构名，就结构体的第一行来说，unsigned char是类型说明符，a是位域名，2是位域长度。哇塞，看着好怪的样子，别着急，请听我慢慢道来。结构体中从上到下依次从低位到高位，也就是说第一行是最低位，最后一行是最高位。这个结构体实际上定义了一个14个比特位域数据结构。假设unsigned char为1个字节，unsigned int为4个字节，请猜猜这个结构体一共有多少字节？7个？这太假了，7个字节还用这位域干什么。2个？感觉还不错，但那明明有个int型，总不会吃干饭的吧。4个，bingo！

怎么会是4个？我们来看看这篇文章给出的解释：

使用位域的主要目的是压缩存储，其大致规则为：

1、如果相邻的两个位域字段的类型相同，且其位宽之和小于其类型的sizeof()大小，则其后面的位域字段将紧邻前一个字段存储，直到不能容纳为止；比如：一个位域变量有三个位域字段a、b、c，且类型完全相同，位域字段a和b的位宽之和小于其类型的sizeof()大小，那么位域字段c紧接着位域字段b后面存储；

2、如果相邻的两个位域字段的类型相同，且其位宽之和大于其类型的sizeof()大小，则后面的位域字段将从下一个存储单元的起始地址处开始存放，其偏移量恰好为其类型的sizeof()大小的整数倍；比如：拿第1点中的例子来说，如果位域字段a和b的位宽之和大于其类型的sizeof()大小，则位域字段c就从下一个存储单元的起始地址初开始存放，其偏移量恰好是其类型的sizeof()大小的整数倍；

3、如果相邻的两个位域字段的类型不同，则各个编译器的具体实现有差异，VC6采取不压缩方式，GCC和Dev-C++都采用压缩方式；

4、如果位域字段之间穿插着非位域字段，则不进行压缩；

5、整个位域结构体的大小为其最宽基本类型成员大小的整数倍；

这。。。你妹啊，不明不白的。那我们来先看这段代码：

struct bitField
{
	unsigned char a:2;
	unsigned char b:3;
	unsigned char c:3;
};

相信你能猜到这个位域的大小是1个字节。即第一个位域字段与第二个位域字段类型相同，相加也没有unsigned char的1个字节（8bit）大，则这里仅仅需要1个字节，第二个位域字段与第三个的类型又相同，三个相加后也没到8bit，则一个字节就够了。那如果再加一段代码：

unsigned char d:5;

那么先看类型，相同，但四个加起来一个字节存不下，就再接一个字节来存储了，结果就是这个结构体要2个字节。那么回到刚才的例子，第四行是int型，int型最宽，就用int型来做结构体大小的单位，也就是说这个结构体只能是int的整数倍大小（4的倍数）。四个字节存这16个bit绰绰有余了，所以大小为4个字节。置于赋值也好说

struct bitField
{
	unsigned char a:2;
	unsigned char b:3;
	unsigned char c:3;
};

struct bitField test;
test.a = 1;
test.b = 2;
test.c = 1;

那么这个这个8比特位域结构体便是00101001。test.c为001，test.b为010，test.c为01。但是无论怎么折腾，这位域的大小还是1个字节的整数倍。看来位域解决不了我的问题，最终还是要用移位。。。

洋洋洒洒码了这么多字，洗洗睡吧，提前祝大家“光棍节”快乐！

programming 8