第12章

位运算与嵌入式编程

C语言测试是招聘嵌入式系统程序员必须且有效的方法。我参加了许多这种测试，在此过程中我意识到这些测试能为面试者和被面试者提供许多有用的信息。此外，撇开面试的压力不谈，这种测试也相当有趣。

从被面试者的角度来讲，你能了解许多关于出题者或监考者的情况。这个测试只是出题者为显示其对ANSI标准细节的知识而不是技术技巧而设计的吗？如要你答出某个字符的ASCII值。这些面试例题着重考查你的系统调用和内存分配策略方面的能力吗？这标志着出题者也许花时间在微机上而不是在嵌入式系统上。如果上述任何问题的答案是“是”的话，那么就得认真考虑是否应该去做这份工作。

从面试者的角度来讲，一个测试也许能从多方面揭示应试者的素质。最基本的，你能了解应试者C语言的水平。应试者是以好的直觉做出明智的选择，还是只是瞎蒙呢？当应试者在某个问题上卡住时是找借口，还是表现出对问题的真正的好奇心，把这看成学习的机会呢？我发现这些信息与面试者们的测试成绩一样有用。

有了这些想法，我们再结合一些真正针对嵌入式系统的考题，希望这些令人头痛的考题能给正在找工作的人一点儿帮助。其中有些题很难，但它们应该都能给你一点儿启迪。

12.1　位制转换

面试例题1：求下列程序的输出结果。［美国某著名计算机硬件公司面试题］

解析：首先参数5为int型，32位平台中为4字节，因此在stack中分配4字节的内存，用于存放参数5。

然后printf根据说明符“%f”，认为参数应该是个double型（在printf函数中，float会自动转换成double），因此从stack中读了8个字节。

很显然，内存访问越界，会发生什么情况不可预料。如果在printf或者scanf中指定了“%f”，那么在后面的参数列表中也应该指定一个浮点数，或者一个指向浮点变量的指针，否则不应加载支持浮点数的函数。

于是("%f",5)有问题，而("%f",5.0)则可行。

答案：

第一个答案是0.000000。

第二个答案是一个大数。

面试例题2：下列程序是否有错？如果有，错在哪里？［美国著名计算机公司I 2007年5月面试题］

解析：结构体位制概念。

答案：

“int z:33;”定义整型变量z为33位，也就是超过了4字节。这是不合法的，会造成越界，所以程序会报错。

面试例题3：Find the defects in each of the following programs, and explain why it is incorrect.（找出下面程序的错误，并解释它为什么是错的。）［中国台湾某著名杀毒软件公司2005年面试题］

解析：这道程序体存在着位运算问题。

答案：val=(val && ~BIT_MASK(pos))这一语句中的“&&”应为“&”。

正确的程序如下所示：

面试例题4：In which system(进制) expression 1316=244 is true?（下面哪个进制能表述1316=244是正确的？）［中国台湾某计算机硬件公司V2010年5月面试题］

A．5

B．7

C．9

D．11

解析：13如果是一个十进制的话，它可以用13=110¹+310⁰来表示。现在我们不知道13是几进制，那我们姑且称其X进制。X进制下的13转化为十进制可以用13=1X¹+3X⁰;表示；X进制下的16转化为十进制可以用16=1X¹+6X⁰;表示；X进制下的244转化为十进制可以用244=2X²+4X¹+4X⁰;表示；因此X进制下的1316=244可以转化为十进制下的等式：(1X¹+3X⁰) (1X¹+6X⁰)=2X²+4X¹+4X⁰。

整理得XX+6X+3X+36=2XX+4X+4；最后得出一元二次方程XX-5*X-14=0。答案X=-2或者X=7。X=-2不合题意舍弃，所以X=7。

答案：B

面试例题5：以下代码哪个等同于int i=(int)p;(p的定义为char *p) ［中国台湾某计算机硬件公司2010年5月面试题］

A．int i=dynamic_cast<int>(p)

B．int i=static_cast<int>(p)

C．int i=const_cast<int>(p)

D．int i=reinterpret_cast<int>(p)

解析：先看这样一段代码：

输出结果如下：

4199056是指针p指向的内容，即p的值"a"强制转化int后的结果。所以(int)"a"的结果也是4199056。reinterpret_cast一定不改变原数据，直接（int）可能也不改变原数据。

因为是把p的值转化为int，二者的二进制模式是一样的，故相同。不存在从char*到int的强制类型转换，static_cast规则比（int）要严格，故static_cast失败。

答案：D

面试例题6：Given the following program snippet, what can we conclude about the use of dynamic_cast in C++?（下面这段程序，我们能总结C++中dynamic_cast的用法是什么？）［中国台湾某计算机硬件公司2010年5月面试题］

A．The dynamic_cast is necessary since we cannot know for certain what concrete type is returned by IWidgetSelector::Selection().（dynamic_cast非常必要，因为我们不知道确定的IWidgetSelector::Selection()返回的具体类型）

B．The dynamic_cast is unnecessary since we know that the concrete type returned by IWidgetSelector::Selection() must be a MyItem object.（dynamic_cast不是必要的，因为我们知道IWidgetSelector::Selection()返回的具体类型一定是一个MyItem对象）

C．The dynamic_cast ought to be a reinterpret_cast since the concrete type is unknown.（dynamic_cast应该是reinterpret_cast，因为具体类型不可知）

D．The dynamic_cast is redundant, the programmer can invoke Activate directly, e.g. ws->Selection()->Activate();（dynamic_cas是多余的，程序员可以直接激活代码，比如ws->Selection()->Activate()）

解析：C++有4个类型转换操作符，这4个操作符是static_cast、const_cast、dynamic_cast和reinterpret_cast。

例如，假设你想把一个int转换成double，以便让包含int类型变量的表达式产生出浮点数值的结果。你应该这样写：

这样的类型转换不论是对人工还是对程序都很容易识别。

在C++中，static_cast在功能上相对C语言来说有所限制。如不能用static_cast像用C风格的类型转换一样把struct转换成int类型，或者把double类型转换成指针类型；另外，static_cast不能从表达式中去除const属性，因为另一个新的类型转换操作符const_cast有这样的功能。

其他C++类型转换操作符被用在需要更多限制的地方。const_cast最普通的用途就是转换掉对象的const属性。通过使用const_cast，让编译器知道通过类型转换想做的只是改变一些东西的constness或者volatileness属性。这个含义被编译器所约束。如果你试图使用const_cast来完成修改constness或者volatileness属性之外的事情，你的类型转换将被拒绝。下面是一个const_cast的例子：

static_cast和reinterpret_cast操作符修改了操作数类型。它们不是互逆的；static_cast在编译时使用类型信息执行转换，在转换执行必要的检测（诸如指针越界计算，类型检查），其操作数相对是安全的。另一方面，reinterpret_cast仅仅是重新解释了给出的对象的比特模型而没有进行二进制转换，编译器隐式执行任何类型转换都可由static_cast显示完成，reinterpret_cast通常为操作数的位模式提供较低层的重新解释。例子如下：

上面的例子中，我们将一个变量从int转换到double。这些类型的二进制表达式是不同的。要将整数9转换到双精度整数9，static_cast需要正确地为双精度整数d补足比特位。其结果为9.0。而reinterpret_cast的行为却不同：

在进行计算以后，d包含无用值。这是因为reinterpret_cast仅仅是复制n的比特位到d，没有进行必要的分析。reinterpret_cast这个操作符被用于的类型转换的转换结果几乎都是实现时定义（implementation-defined）。因此，使用reinterpret_casts的代码很难移植。转换函数指针的代码是不可移植的，（C++不保证所有的函数指针都被用一样的方法表示），在一些情况下这样的转换会产生不正确的结果。所以应该避免转换函数指针类型，按照C++新思维的话来说，reinterpret_cast是为了映射到一个完全不同类型的意思，这个关键词在我们需要把类型映射回原有类型时用到它。我们映射到的类型仅仅是为了故弄玄虚和其他目的，这是所有映射中最危险的。reinterpret_cast就是一把锐利无比的双刃剑，除非你处于背水一战和火烧眉毛的危急时刻，否则绝不能使用。

对于dynamic_cast要注意以下4点：

●　dynamic_cast是在运行时检查的，dynamic_cast用于在继承体系中进行安全的向下转换downcast（当然也可以向上转换，但是没必要，因为完全可以用虚函数实现），即基类指针／引用到派生类指针／引用的转换。如果源和目标类型没有继承／被继承关系，编译器会报错；否则必须在代码里判断返回值是否为NULL来确认转换是否成功。

●　dynamic_cast不是扩展C++中style转换的功能，而是提供了类型安全性。你无法用dynamic_cast进行一些“无理”的转换。

●　dynamic_cast是4个转换中唯一的RTTI操作符，提供运行时类型检查。

●　dynamic_cast不是强制转换，而是带有某种“咨询”性质的。如果不能转换，dynamic_cast会返回NULL，表示不成功。这是强制转换做不到的。

下面是一个例子：

在本题中，MyItem与IGlyph是继承关系，可以适用dynamic_cast类型转换，而因为我们不知道确定的IWidgetSelector::Selection()返回的具体类型是什么，所以应用dynamic_cast“试探性”地进行类型转换是十分必要的。

答案：A

面试例题7：阅读下面程序，下列选项说法正确的是哪项？［德国某计算机软件公司2009年12月面试题］

A．标识1处有问题，Class A不应该调用虚函数。

B．标识2处有问题，(dynamic_cast <B*>(pa))->FunctionB();无法运行通过。

C．标识3处有问题，(dynamic_cast <B*>(pa))->foo();无法运行通过。

D．标识4处有问题，(dynamic_cast <B*>(pa))->pp();无法运行通过。

因为a是基类对象，所以dynamic_cast <B*>(pa）将返回空指针。

解析：在上面的代码段中，如果pa指向一个B类型的对象，对这种情况执行任何操作都是安全的；但是，实际上pa指向的是一个A类型的对象，那么(dynamic_cast <B*>(pa))返回值将是一个空指针，所以题目中的代码：

与下列代码：

没有任何区别，之所以标识2和标识4可以运行通过，是因为FunctionB和pp函数未使用任何成员数据，也不是虚函数，不需要this指针，也不需要动态绑定，可正常运行。

而(dynamic_cast <B*>(pa))->foo();将导致程序崩溃，因为调用了虚函数，编译器需要根据对象的虚函数指针查找虚函数表，但此时是空，为非法访问。

如果将A a；改为B b；就可正常运行了，正确代码如下：

答案：C

面试例题8：下面程序的运行结果是什么？［美国某著名计算机软硬件公司面试题］

解析：此题有两个考点，一是用最有效率的方法算出2乘以8等于几，二是无符号结果问题。

在这里，8左移一位就是8×2的结果16。移位运算是最有效率的计算乘／除算法的运算之一。在unsigned short int中无符号的–1的结果等于65535。

答案：16，65535

面试例题9：建立一个联合体，由char类型和int类型组成。下面的程序运行结果是什么？

解析：内存中数据的排列问题。

答案：

运行上面程序后，输出为：

这说明，内存中数据低位字节存入低地址，高位字节存入高地址，而数据的地址采用它的低地址来表示。

面试例题10：嵌入式系统总是要用户对变量或寄存器进行位操作。给定一个整型变量a，写两段代码，第一个设置a的bit 3，第二个清除a的bit 3。在以上两个操作中，要保持其他位不变。

解析：被面试者对这个问题有3种基本的反应。

一种是不知道如何下手。显然该被面试者从没做过任何嵌入式系统的工作。

还有一种是用bit fields。bit fields是被扔到C语言死角的东西，它保证你的代码在不同编译器之间是不可移植的，同时也保证了你的代码是不可重用的。

还有一种是用#defines和bit masks操作。这是一个有极高可移植性的方法，是应该被用到的方法。

一些人喜欢为设置和清除值而定义一个掩码，同时定义一些说明常数，这也是可以接受的。面试官希望看到的几个要点为说明常数、“|=”和“&=~”操作。

答案：

最佳的解决方案如下：

面试例题11：阅读以下代码，写出程序运行结果。［中国著名杀毒软件企业J公司2008年4月面试题］

解析：15×4（字节）=60

所以要求输出的十六进制结果是3C。这样在大系统里面使用未初始化的指针是很危险的。

答案：3C

12.2　嵌入式编程

面试例题1：Interrupts are an important part of embedded systems. Consequently, many compiler vendors offer an extension to standard C to support interrupts. Typically, the keyword is _interrupt. The following routine(ISR). Point out the errors in the code.（中断是嵌入式系统中重要的组成部分，这导致了很多编译开发商提供一种扩展——让标准C支持中断。其代表事实是，产生了一个新的关键字_interrupt。请看下面的程序（一个中断服务子程序ISR），请指出这段代码的错误。）［中国台湾某著名CPU生产公司2005年面试题］

解析：嵌入式编程问题。

答案：

（1）ISR不能返回一个值。如果你不懂这个，那么是不会被雇用的。

（2）ISR不能传递参数。如果你没有看到这一点，被雇用的机会等同第一项。

（3）在许多处理器／编译器中，浮点一般都是不可重入的。有些处理器／编译器需要让额外的寄存器入栈，有些处理器／编译器就不允许在ISR中做浮点运算。此外，ISR应该是短而有效率的，在ISR中做浮点运算是不明智的。

（4）与第三点一脉相承，printf()经常有重入和性能上的问题，所以一般不使用printf()。

面试例题2：In embedded system, we usually use the keyword “volatile”, what does the keyword mean?（在嵌入式系统中，我们经常使用“volatile”这个关键字，它是什么意思？）［中国台湾某著名CPU生产公司2005年面试题］

解析：volatile问题。

当一个对象的值可能会在编译器的控制或监测之外被改变时，例如一个被系统时钟更新的变量，那么该对象应该声明成volatile。因此编译器执行的某些例行优化行为不能应用在已指定为volatile的对象上。

volatile限定修饰符的用法与const非常相似——都是作为类型的附加修饰符。例如：

display_register是一个int型的volatile对象；curr_task是一个指向volatile的Task类对象的指针；ixa是一个volatile的整型数组，数组的每个元素都被认为是volatile的；bitmap_buf是一个volatile的Screen类对象，它的每个数据成员都被视为volatile的。

volatile修饰符的主要目的是提示编译器该对象的值可能在编译器未监测到的情况下被改变，因此编译器不能武断地对引用这些对象的代码做优化处理。

答案：

volatile的语法与const是一样的，但是volatie的意思是“在编译器认识的范围外，这个数据可以被改变”。不知什么原因，环境正在改变数据（可能通过多任务处理），所以，volatile告诉编译器不要擅自做出有关数据的任何假定——在优化期间这是特别重要的。如果编译器说：“我已经把数据读进寄存器，而且再没有与寄存器接触。”在一般情况下，它不需要再读这个数据。但是，如果数据是volatile修饰的，编译器则不能做出这样的假定，因为数据可能被其他进程改变了，编译器必须重读这个数据而不是优化这个代码。

就像建立const对象一样，程序员也可以建立volatile对象，甚至还可以建立const volatile对象。这个对象不能被程序员改变，但可通过外面的工具改变。

面试例题3：关键字const有什么含意？下面的声明都是什么意思？

解析：只要一听到被面试者说“const意味着常数”，面试官就知道自己正在和一个业余者打交道。因为ESP（Embedded Systems Programming，嵌入式系统编程）的每一位求职者都应该非常熟悉const能做什么和不能做什么。正确的说法是能说出const意味着“只读”就可以了。尽管这个答案不是完全的答案，但面试官可以接受它为一个正确的答案。

关键字const的作用是为读你代码的人传达非常有用的信息。实际上，声明一个参数为常量是为了告诉用户这个参数的应用目的。如果你曾花很多时间清理其他人留下的垃圾，你就会很快学会感谢这点儿多余的信息。当然，懂得用const的程序员很少会留下垃圾让别人来清理。通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码。

合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。

答案：前两个的作用是一样的。a是一个常整型数（不可修改值的整型数）。第三个意味着a是一个指向常整型数的指针（也就是说，整型数是不可修改的，但指针可以修改）。第四个的意思是a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。最后一个意味着a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。

面试例题4：关键字volatile有什么含意？并给出3个不同的例子。［中国台湾某著名计算机硬件公司面试题］

解析：回答不出这个问题的人是不会被雇用的。我认为这是区分C程序员和嵌入式系统程序员的最基本的问题。搞嵌入式的家伙们经常同硬件、中断、RTOS等打交道，所有这些都要求用到volatile变量。不懂得volatile的内容将会带来灾难。

答案：一个定义为volatile的变量是说这变量可能会被意想不到地改变，这样，编译器就不会去假设这个变量的值了。精确地说就是，优化器在用到这个变量时必须每次都小心地重新读取这个变量的值，而不是使用保存在寄存器里的备份。下面是volatile变量的几个例子：

●　并行设备的硬件寄存器（如状态寄存器）。

●　一个中断服务子程序中会访问到的非自动变量（Non-automatic variables）。

●　多线程应用中被几个任务共享的变量。

面试例题5：一个参数可以既是const又是volatile吗？一个指针可以是volatile吗？解释为什么。

答案：

第一个问题：可以。一个例子就是只读的状态寄存器。它是volatile，因为它可能被意想不到地改变；它又是const，因为程序不应该试图去修改它。

第二个问题：可以。尽管这并不很常见。一个例子是当一个中断服务子程序修改一个指向一个buffer的指针时。

面试例题6：下面的函数有什么错误？

解析：这段代码的目的是用来返还指针ptr指向值的平方，但是，由于ptr指向一个volatile型参数，编译器将产生类似下面的代码：

由于*ptr的值可能被意想不到地改变，因此a和b可能是不同的。结果，这段代码可能无法返回你所期望的平方值。

答案：

正确的代码如下：

面试例题7：嵌入式系统经常具有要求程序员去访问某特定位置的内存的特点。在某工程中，要求设置一绝对地址为0x67a9的整型变量的值为0xaa66。编译器是一个纯粹的ANSI编译器。写代码去完成这一任务。

解析：这一问题测试你是否知道为了访问一个绝对地址把一个整型数强制转换（typecast）为一个指针是合法的。这一问题的实现方式随着个人风格不同而不同。典型的代码如下：

一个较晦涩的方法是：

建议你在面试时使用第一种方案。

答案：

面试例题8：评价下面的代码片断，找出其中的错误。

解析：这一问题真正能揭露出应试者是否懂得处理器字长的重要性。在笔者的眼中，好的嵌入式程序员应该非常准确地明白硬件的细节和它的局限，然而PC程序往往把硬件作为一个无法避免的烦恼。对于一个int型且不是16位的处理器来说，上面的代码是不正确的。

答案：应编写如下代码：

面试例题9：下面的代码片段的输出是什么？为什么？

解析：这是一道动态内存分配（Dynamic memory allocation）题。

尽管不像非嵌入式计算那么常见，嵌入式系统还是有从堆（heap）中动态分配内存的过程。

面试官期望应试者能解决内存碎片、碎片收集、变量的执行时间等问题。

这是一个有趣的问题。故意把0值传给了函数malloc，得到了一个合法的指针，这就是上面的代码，该代码的输出是“Got a valid pointer”。我用这个来讨论这样的一道面试例题，看看被面试者是否能想到库例程这样做是正确的。得到正确的答案固然重要，但解决问题的方法和你做决定的基本原理更重要。

将程序修改成：

或者：

如果求ptr的strlen值和sizeof值，该代码的输出是“Got a null pointer”。

答案：Got a valid pointer。

面试例题10：In little-endian systems, what is the result of following C program? (在小尾字节系统中，这段C程序的结果是多少？)

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

我们一般将Endian翻译成“字节序”，将big Endian和little Endian称做“大尾”和“小尾”。Little-Endian主要用在我们现在的PC的CPU中，Big-Endian则应用在目前的Mac机器中（注意：是指Power系列处理器）

嵌入式系统开发者应该对Little-endian和Big-endian模式非常了解。采用Little-endian模式的CPU对操作数的存放方式是从低字节到高字节，而Big-endian模式对操作数的存放方式是从高字节到低字节。例如，16bit宽的数0x1234在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：

而在Big-endian模式CPU内存中的存放方式则为：

32bit宽的数0x12345678在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：

而在Big-endian模式CPU内存中的存放方式则为：

在本题中E的ASCII值是0x45(0100 0101)，M是0x4D(0100 1101)，它们在内存中的表现如下：

结构bitstruct是9位的，执行copy以后，b在内存中如下：

b1占5位：

中间跳过2位，b2占2位：

计算的时候再把它们逆转过来，就成了下面的形式：

b1最高位是0，表示其是正数，其原码跟补码一致，所以b1=2^0＋2^2=5。

b2最高位是1，表示其是负数，其原码要进行取反操作再加1为10所以b2=-(2^1)=(-2)。

答案：5，-2

面试例题11：在某些极端要求性能的场合，我们需要对程序进行优化，关于优化，以下说法正确的是：

A．将程序整个用汇编语言改写会大大提高程序性能。

B．在优化前，可以先确定哪部分代码最为耗时，然后对这部分代码使用汇编语言编写。使用的汇编语句数目越少，程序就运转越快。

C．使用汇编语言虽然可能提高了程序性能，但是降低了程序的可移植性和可维护性，所以应该绝对避免。

D．适当调整汇编指令的顺序，可以缩短程序运行的时间。

解析：AC说法都过于绝对了。至于B也是错的，不同的架构有不同的流水线方式，arm9中的流水线对汇编的顺序要求很高，不然会浪费指令周期，有时候甚至用nop填充。

答案：D

面试例题12：使用C语言将一个1GB的字符数组从头到尾全部设置为字符“A”，在一台典型的当代PC上，需要花费的CPU时间的数量级最接近：

A．0.001秒

B．1秒

C．100秒

D．2小时

解析：1GB需要1G条指令，如4核2GB的cpu，如1周期1条指令，需要0.25秒，所以最接近1秒。

答案：B面试例题13：十进制数-10的三进制4位数补码形式是_：

A．0101

B．1010

C．2121

D．2122

解析：对于负数的补码：对于二进制而言，-10的补码为-(2^8-|-10|)=-(256-10)=-246=11110110。

同理，对于4位三进制的补码：10的补码为3^4 - |-10|=71=2212。

答案：D

12.3　static

面试例题1：关键字static的作用是什么？

解析：这个简单的问题很少有人能回答完全。大多数应试者能正确回答第一部分，一部分能正确回答第二部分，但是很少的人能懂得第三部分。这是一个应试者的严重的缺点，因为他显然不懂得本地化数据和代码范围的好处和重要性。

答案：在C语言中，static关键字至少有下列几个作用：

●　函数体内static变量的作用范围为该函数体，不同于auto变量，该变量的内存只被分配一次，因此其值在下次调用时仍维持上次的值。

●　在模块内的static全局变量可以被模块内所有函数访问，但不能被模块外其他函数访问。

●　在模块内的static函数只可被这一模块内的其他函数调用，这个函数的使用范围被限制在声明它的模块内。

●　在类中的static成员变量属于整个类所拥有，对类的所有对象只有一份拷贝。

●　在类中的static成员函数属于整个类所拥有，这个函数不接收this指针，因而只能访问类的static成员变量。

面试题目2：写出下面程序的运行结果。

解析：在求和函数sum里面c是auto变量，根据auto变量特性得知，每次调用sum函数时变量c都会自动赋值为0。b是static变量，根据static变量特性得知，每次调用sum函数时变量b都会使用上次调用sum函数时b保存的值。

简单地分析一下函数，可以知道，若传入的参数不变，则每次调用sum函数返回的结果，都比上次多2。所以答案是：8,10,12,14,16。

答案：8,10,12,14,16。