笔试中的几个常考题

伊海 · 发表于 2014-11-29 19:32:18

1.1 strcpy
1. 已知strcpy函数的原型是char *strcpy(char *strDest, const char *strSrc); 其中strDest是目的字符串，strSrc是源字符串。不调用C++/C的字符串库函数，请编写函数 strcpy。

char *strcpy(char *strDest, const char *strSrc)
{
assert((strDest!=NULL) && (strSrc !=NULL));
char *address = strDest;
while( (*strDest++ = * strSrc++) != ‘\0’ )
NULL ;
return address ;
}

复制代码

这个题目创维和华为都曾用来做为考题。
在程序开头我们肯定要断言strDest和strSrc不等于NULL，assert()的作用是：断言是一个包含布尔表达式的语句，在执行这个语句时假定该表达式为 true。如果表达式计算为 false，那么系统会报告一个 Assertionerror。
我们注意到返回值是char *类型！这里是为了实现链式表达式。
将这个题目再引申下，已知strncpy的函数原型是char *strncpy( char *to, const char *from, size_t count );
其中to是目的字符串，from是源字符串。不调用C++/C的字符串库函数，请编写函数 strncpy。
提示：将字符串from 中至多count个字符复制到字符串to中。如果字符串from 的长度小于count，其余部分用'\0'填补。返回处理完成的字符串。

char *strncpy(char *to, const char *from , size_t count )
{
assert((to!=NULL) && (from !=NULL));
char *address = to;
while( count != 0 )
{
*address++ = *from++ ;
if ( *from == '\0')
{
*address++ = '\0' ;
}
count-- ;
}
return address ;
}

复制代码

1.2 CPU的使用率
1. 写一个程序，让你的电脑CPU使用率一直运行在50%。

#include <iostream>
#include <stdlib.h>
using namespace std;
/* 让CPU的使用率在50% */
int main(int argc, char *argv[])
{
for( ; ; )
{
for( int i = 0 ; i < 800000000 ; i++ ) ;
_sleep(10) ;
}
return 0;
}

复制代码

这里的800000000是根据我自己电脑算出来的，因为我的电脑主频是2.0GHz。
留一个问题给读者，怎样让自己的电脑CPU以正弦曲线运行？
注意：对于新代处理器由于优化，可能做不到。

1.3 二进制数据中1的个数
1. 写一个程序，随意输入x，输出x的二进制数据中1的个数。
这个程序的算法很多，可以一位一位右移进行测试，也有其他办法。右移法我就不再累赘，这个方法简单，但是时间复杂度会比较大。看看下面这个方法：

int number( unsigned int x )
{
unsigned int countx = 0;
while (x) {
countx ++ ;
x = x&(x-1) ;
}
return countx ;
}

复制代码

如果x大于0，那么x一定有一位为1，所以进入while之后countx先加1。如果x=100,那么经过x=x&(x-1)，x为0，countx为1，此时结束程序。

1.4 二进制高位到低位实现逆变
1. 编写一个函数，实现将一个32位int型数据的二进制高位到低位实现逆变，例如：1101 0101变成1010 1011。
这个题目的解决方法很多，代表性的有两种。

int func(unsigned int uiData , int length)
{
unsigned int uiValue = 0 ;
int i = 0 ;
for ( i = 0 ; i < length ; i++ )
{
uiValue = (uiValue << 1) + (uiData & 0x01) ;
uiData = uiData >> 1 ;
}
return uiValue ;
}

复制代码

这个方法比较常见，通过移位的方法将高位到低位实现逆序。但是这个方法存在唯一的不足之处是效率低，要进行32次移位和运算。

int func (unsigned int uiData)
{
unsigned int uiValue = 0 ;
/* 分而治之的思想 */
/* 高16位和低16互换 */
uiValue = ((uiData >> 16)&0x0000ffff) |
((uiData << 16)&0xffff0000);
/*高低16位中的高低8位互换*/
uiValue = ((uiValue >> 8)&0x00ff00ff) |
((uiValue << 8)&0xff00ff00);
/*8位中的高低4位互换*/
uiValue = ((uiValue >> 4)&0x0f0f0f0f) |
((uiValue << 4)&0xf0f0f0f0);
/*4位中的高低2位互换*/
uiValue = ((uiValue >> 2)&0x33333333) |
((uiValue << 2)&0xcccccccc);
/*2位中的高低位互换*/
uiValue = ((uiValue >> 1)&0x55555555) |
((uiValue << 1)&0xaaaaaaaa);
return uiValue ;
}

复制代码

这个程序只需要位操作5次，就能实现高位到低位的逆序。我们逐句程序分析一下。假设uiData = 1100 0101 0101 1100 1100 0101 0101 1111。执行完成下面这句程序，

/* 高16位和低16互换 */
uiValue = ((uiData >> 16)&0x0000ffff) | ((uiData << 16)&0xffff0000);
得到1100 0101 0101 1111 1100 0101 0101 1100，也就是高16位和低16位互换。
执行完成：
/*高低16位中的高低8位互换*/
uiValue = ((uiValue >> 8)&0x00ff00ff) | ((uiValue << 8)&0xff00ff00);
得到0101 1111 1100 0101 0101 1100 1100 0101，也就是高低16位中高8位和低8位互换。
执行完成：
/*8位中的高低4位互换*/
uiValue = ((uiValue >> 4)&0x0f0f0f0f) | ((uiValue << 4)&0xf0f0f0f0);
得到1111 0101 0101 1100 1100 0101 0101 1100，也就是从高位起，每8位段的高4位和低4位完成互换。
执行完成：
/*4位中的高低2位互换*/
uiValue = ((uiValue >> 2)&0x33333333) | ((uiValue << 2)&0xcccccccc);
得到1111 0101 0101 0011 0011 0101 0101 0011，也就是从高位起，每4位段的高2位和低2位完成互换。
执行完成：
/*2位中的高低位互换*/
uiValue = ((uiValue >> 1)&0x55555555) | ((uiValue << 1)&0xaaaaaaaa);
得到1111 1010 1010 0011 0011 1010 1010 0011。也就是从高位起，每2位段的高1位和低1位完成互换。和原始数据1100 0101 0101 1100 1100 0101 0101 1111进行对比，逆序。

1.5 大小端测试
1. 编写一个函数，测试MCU是大端模式存储还是小端模式存储。

/****************************************************************
** 函数名称：LBEndian
** 函数功能：大小端测试函数
** 入口参数：None
** 出口参数：1 or 0
****************************************************************/
int LBEndian (void)
{
unsigned int uiNumber = 0x12345678 ;
unsigned char *ucptr = (void *)0 ;
/* 将最低位1一个字节赋给ucptr */
ucptr = (unsigned char *)(&uiNumber) ;
/* 如果是小段模式，则返回1*/
if ( 0x78 == (*ucptr) )
{
return 1 ;
}
/* 如果是大端模式，则返回0 */
else
{
return 0 ;
}
}

复制代码

ucptr = (void *)0 ,这样做是为了防止野指针的危患。通过ucptr = (unsigned char *)(&uiNumber) (好好理解这句程序);截取低地址的存储字节数据，如果低地址存储的是低字节，那么就是小端模式，如果低字节存储的是高字节，那么就是大端模式。

1.6 二分查找
1. 写一个函数实现二分查找

int BinarySeach(int *iArray, int key, int n)
{
int iLow = 0 ;
int iHigh = n - 1;
int iMid;
while (iLow <= iHigh)
{
iMid = (iHigh + iLow)/2;
if (iArray[iMid] > key)
{
iHigh = iMid - 1 ;
}
else if (iArray[iMid] < key)
{
iLow = iMid + 1 ;
}
else
{
return iMid ;
}
}
}

复制代码

数据结构中的各种查找算法在笔试中是无处不在，在工程应用中也是“无孔不入”。所以作为一个软件工程师，必须牢牢掌握各种查找算法。
1.7    int (*p[10])(int)
1. int (*p[10])(int) 表示的是什么？
函数指针数组，int(*p)(int)，我们知道这是一个函数指针，一个指向int Fun(int)函数的指针，那么int (*p[10])(int)即为函数指针数组。

1.8    对绝对地址赋值的问题
涉及到内存的问题，都让很多人望而却步，因为内存确实是地雷阵，稍不小心就会引爆。
1. 要对绝对地址0x10 0000赋值，我们该怎么做？
*(unsigned  int  *)0x10 0000 = 1234 ;
通过这个程序我们把常量1234存储在地址为0x10 0000。
2. 如果想让程序跳转到绝对地址为0x10 0000去执行，应该怎么做？
*(  (void (*)( ))0x100000 ) ( );
首先要将0x10 0000转换成函数指针：
(void (*)( ))0x100000
然后再调用他：
*(  (void (*)( ))0x100000  ) () ;
因为内存是摸不着，猜不透的，所以很像地雷阵，随时都可能挂掉。