Thronds

一问你会什么 二问你做出过什么 三问你为了什么

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 56 评论 :: 0 Trackbacks
    在求职笔试中,C中的位域是一个常考点,特别是在嵌入式软件中更常见。位域的最大好处是可以根据自己需要定制位数,从而节省空间,例如:嵌入式编程稀缺的内存资源。还有在网络通讯中,对头信息部分的结构定义也常用到位域,少传一位是一位啊。
    这里来分析EMC的一道笔试题(07年招聘试题):
1 typedef struct bitstruct 2 { 3 int b1:5; 4 int :2; 5 int b2:2; 6 }bitstruct; 7 int main(int argc, char *argv[]) 8 { 9 bitstruct b; 10 printf("%d\n",sizeof(bitstruct)); 11 memcpy(&b,"EMC Examination",sizeof(b)); 12 printf("%d,%d\n",b.b1,b.b2); 13 return 0; 14 }
请问在little-endian systems(系统默认的存放顺序)中,输出结果是什么?
答案是
4 
5-2

所需知识点:
1.位域的概念和特点
    C语言允许在一个结构体中以位为单位来指定其成员所占内存长度,这种以位为单位的成员称为“位段”或称“位域”(bit field)。(1)位段成员的类型必须指定为unsigned或int类型;(2)若某一位段要从另一个字开始存放,用:0长度为0的空位段,作用就是使下一个位段从下一个存储单位(视不同编译系统而异)开始存放;(3)一个位段必须存储在同一存储单元中,不能跨两个单元;(4)可以定义无名字段例如":2";(5)位段的长度不能大于存储单元的长度,也不能定义位段数组;(6)位段可以用整形格式符输出;(7)位段可以在数值表达式中引用,它会被系统自动地转换成整形数。[1][3]

2.Little-endian systems的内存布局特点
   
    先问一个问题:Endian这个词是什么意思?

    “endian”这个词出自《格列佛游记》。小人国的内战就源于吃鸡蛋时是究竟从大头(Big-Endian)敲开还是从小头(Little-Endian)敲开,由此曾发生过六次叛乱,其中一个皇帝送了命,另一个丢了王位。

    我们一般将endian翻译成“字节序”,将big endian和little endian称作“大尾”和“小尾”。这也在当今的CPU派别中一样存在。Motorola的PowerPC系列CPU采用的Big-endian, Intel的X86系列CPU采用的是Little-endian。Little-endian的特点是高高低低,即高位地址存放最高有效字节,低位地址存放最低有效字节;而Big-endian正好相反。下面用图的方式说明起来更直观,例如0x12345678(特别注意,这是单个数,不是字符串,如果是字符串就不一定这样了。之前没有特别注意这点,害的我多花了冤枉时间)。
Big Endian

   低地址                                            高地址
   ----------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     12     |      34    |     56      |     78    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Little Endian

   低地址                                            高地址
   ----------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     78     |      56    |     34      |     12    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    上面的字节序的不同,在单机的操作中没有问题,因为一台单机就是采用单一的字节序嘛!但是在两个不同的主机进行协作时,就会出现问题了;另外在网络通讯中也同样会出现问题,详细参考[2]

就单个字节而言,也会有这样的问题:比特序有差别吗?

    也分成两种序,如果我们处理的基本单位是字节以上的话,对此就不必担心了,因为CPU存储操作的最小单元是字节,所以比特位的顺序对我们来就是透明的,我们在读取某个字节时,不管它用的是Big endian 还是Little endian,我们读到的都是一个同样的字节,只不过硬件在读写时的顺序,一个是从高到底另一个是从低到高,对我们的使用不产生影响。但是如果涉及到位域的存放问题,还是要特别小心,上面这道题就是一个非常的好的例子。

Big Endian

   msb                                                         lsb
   ---------------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   1  |   0  |   1  |   1  |   0  |   1  |   0  |   0  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Little Endian

   lsb                                                         msb
   ---------------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   0  |   0  |   1  |   0  |   1  |   1  |   0  |   1  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


3.memcpy()与strcpy()的区别
    这个问题很简单,可以想象成这样:memcpy的基本单位是位,strcpy的基本单位是字符。所以,memcpy会根据提供的长度完全按位拷贝,而strcpy是两个字符串之间的拷贝。

    回来原来的问题上,在采用little endian的BUS64中,struct bitstruct在没涉及到高低位问题时,也就是我们平时常会画出的一种形式是:
{b1 b1 b1 b1 b1 Ø Ø b2   b2 Ø Ø Ø Ø Ø Ø Ø    ØØØØØØØØ   ØØØØØØØØ};
在内存中的实际布局是:

   低地址                                                 高地址
   -------------------------
------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-+-+-+-+-+-+-+-+-+
   | b2 Ø Ø b1 b1 b1 b1 b1 |Ø Ø Ø Ø Ø Ø Ø b2 |ØØØØØØØØ |ØØØØØØØØ |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-+-+-+-+-+-+-+-+-+

Ø表示空填充,这当中包含一个原则:一个位域的存放不可以跨字存放,但可以跨字节存储;这里采用的比特续也是little endian,说明了比特序对操作也是有影响的嘛!

    memcpy按位拷贝“EMC Examination”到b中,一个字符是8位; 又因为sizeof(b)=4,所以只写入"EMC "。"EMC "对应的位序列是:{0100 0101  0100 1101  0100 0011  0010 0000},从这里写到内存里的形式是:(在这里不要被little endian给迷惑了,E不是放在高地址,参看上面红色的特别注意

   低地址                                                 高地址
   -------------------------
------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-+-+-+-+-+-+-+-+-+
   | b2 Ø Ø b1 b1 b1 b1 b1 |Ø Ø Ø Ø Ø Ø Ø b2 |ØØØØØØØØ |ØØØØØØØØ |
   | 0  1 0 0  0  1 0  1 |0  1  0  0 1  1 0  1 |0100 0011     |0010 0000    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

printf("%d,%d\n",b.b1,b.b2);读出来的b1是00101,它的值是5; b2是10,转换成十进制是-2。


到了这一步,似乎题目已经解答出来了,但还有两个地方有疑惑:
1.struct bitstruct在内存中的位存放顺序是这样的么?
   低地址                                                 高地址
   -------------------------
------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-+-+-+-+-+-+-+-+-+
   | b2 Ø Ø b1 b1 b1 b1 b1 |Ø Ø Ø Ø Ø Ø Ø b2 |ØØØØØØØØ |ØØØØØØØØ |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

2.memcpy函数在按位拷贝时的拷贝顺序是这样的么?
   低地址                                                 高地址
   -------------------------
------------------------------------->
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-+-+-+-+-+-+-+-+-+
   | 01000101 | 01001101 |0100 0011 |0010 0000 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
关于上面两个问题的验证工作留给路过的朋友来做:-P .....  欢迎批评指正

[1]谭浩强 C程序设计 第二版 清华大学出版社
[2]http://blog.csdn.net/sunshine1314/archive/2008/04/20/2309655.aspx
[3]http://topic.csdn.net/t/20061207/10/5212742.html#
[4]http://elanso.com/ArticleModule/LmT3M6M6HGKzTDQcPKMGKAIi.html
[5]关于字节序与编码的关联请参考http://elanso.com/ArticleModule/LmT3M6M6HGKzTDQcPKMGKAIi.html
posted on 2008-12-06 16:17 thronds 阅读(6273) 评论(9)  编辑 收藏 引用 所属分类: C++技术面试题

评论

# re: C中的位域 2009-12-08 22:54 haohaoking
哥们,你这文章写得,还是删除了吧~  回复  更多评论
  

# re: C中的位域 2010-06-20 00:20 bobluo
写得很好,图文并茂,但是有点问题。
你的结果是对的,但是内存布局反了:
实际的内存布局:
低地址 高地址
-------------------------------------------------------------->
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| b1 b1 b1 b1 b1 Ø Ø b2 | b2 Ø Ø Ø Ø Ø Ø Ø |ØØØØØØØØ |ØØØØØØØØ |
| 1 0 1 0 0 0 1 0 |1 0 1 1 0 0 1 0 |11000010|00000100|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1)b1对应的内存内容为
(低地址)--------->(高地址)
101000
在little-endian里面比特序的低地址的bit是低有效位,高地址的bit是高有效位,因此对应的数值要反过来看,为0x000101,即5
2)b2对应的内存内容为
(低地址)--------->(高地址)
01
同样,对应的数值为0x10,即-2。

当然,你这样的话ascii码都是从左向右读(低地址在左),比较符合人的习惯,但是little-endian的话,ascii码在内存中的实际布局正好相反。而位域无论大小端序,都是从低地址到高地址依次存放的,不会出现你说的这种b2的两位相隔如此之远的情况,这和位域本身的目的背道而驰
  回复  更多评论
  

# re: C中的位域 2010-06-20 00:29 bobluo
另外有个错误,你专门用红色标出来的特别注意是错的,strcpy和memcpy的结果是一样的,不存在你所说的差别。都是按字节拷贝,而且字节在内存中的比特序受大小端序的影响。而非你说的不要受小端序迷惑。如果是大端序,那么是
低地址 高地址
-------------------------------------------------------------->
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| b1 b1 b1 b1 b1 Ø Ø b2 |b2 Ø Ø Ø Ø Ø Ø Ø |ØØØØØØØØ |ØØØØØØØØ |
| 0 1 0 0 0 1 0 1 |0 1 0 0 1 1 0 1 |0100 0011|0010 0000|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  回复  更多评论
  

# re: C中的位域 2010-11-25 10:26 newmalloc
其实,这个问题不用搞得那么复杂;
每个bit在内存中的分布顺序,在拷贝的时候由Memcpy来负责对齐,我们要弄清的是b1的5 bits是字节的低位开始分布的,那么只需要知道E的asic是0x45,找到最低5位,即00101b,即可知道b1=5;b2也是同样的道理  回复  更多评论
  

# re: C中的位域 2011-09-08 12:41 digdeep126
#include <stdio.h>
struct mystr_t {
unsigned short f1:12;
unsigned short f2: 4;
};
int main()
{
struct mystr_t st;
unsigned char *pst;

st.f1 = 0xFFF;
st.f2 = 0x9;

pst = (unsigned char *)&st;
printf("%x %x\n", pst[0], pst[1]);

return 0;
}
结果显示为:
FF 9F

按照你们的理解,请解释这里的结果(gcc编译运行)。

原因是:
编译器调整了 struct mystr_t。编译将f2放到前面去了,而f1放到了后面。还有由于cpu是小端序。

所以说,位域在内存中的存放,要看情况,并不是一定是“在little-endian里面比特序的低地址的bit是低有效位,高地址的bit是高有效位”!  回复  更多评论
  

# re: C中的位域 2012-09-21 18:26 拉拉
@bobluo
这哥们别随便说别人不对,根据我的机器验证,楼主说的内存布局是很正确的。  回复  更多评论
  

# re: C中的位域 2012-09-21 18:31 拉拉
@digdeep126
真正的原因是:内存布局为(第一字节)f1 f1 f1 f1 f1 f1 f1 f1,(第二字节)f2 f2 f2 f2 f1 f1 f1 f1, 按字节取当然就是 ff 9f 啦  回复  更多评论
  

# re: C中的位域 2012-09-21 18:32 拉拉
但是这里的 -2 是怎会回事?求指教,为什么一定是负的?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理