A Za, A Za, Fighting...

坚信:勤能补拙

给C瓜同学吧

C瓜同学一直关注这个我这个小地方,下面是一些我面试中或者和同学讨论的一些不错的面试题,备份一下,也希望对你有用。

1:C++的多态是如何实现的?如果你用C如何来实现面向对象的多态?
解:
C++多态的实现主要依赖虚函数表,以及每个对象中指向虚函数表的指针
至于如何用C来实现面向对象的多态,我觉得比较靠谱的方法是函数指针,通过赋予函数指针不同的函数(地址)来调用不同的函数,得到不同的结果

2:判断一个有向图中是否有环。上篇文章里面写的那个杯子倒水问题。给一个都是正整数的数组,和一个正整数sum,求是否存在和为sum的子数列。
解:
【判断一个有向图是否有环】

【杯子倒水问题】
把所有可能的操作列出来,宽度优先搜索,从初始状态到结束状态

【给一个都是正整数的数组,和一个正整数sum,求是否存在和为sum的子数列】

联想到的问题有:
a. 给一个都是正整数的数组,是否存在两个数的和为某个给定的sum? 三个数呢?
针对两个数的情况,可以先排序,然后一个指针front指向第一个元素(最小),一个指针tail指向最后一个元素(最大),如果*front + *tail < sum, ++front, 如果*front + *tail > sum, --tail;
如果三个数,或者N个数,该如何做?

动态规划,类似于01背包问题
f[i][k]表示前i个元素中任意k个元素的和的集合,那么有:
                 f[i][k] = f[i-1][k] + (f[i-1][k-1] + array[i])
or:
f[i][v]表示前i个元素中是否存在和的v的子数列,那么有:
                 f[i][v] = 1, only if f[i-1][v]=1 or f[i-1][v-array[i]]=1

3:两个有大量id的集合A和B,数量上亿级,如何求出两个集合的交集,A中有的B中没有的,和B中有的A中没有的集合。
涉及海量数据处理: 二分搜索、位图Bitmap、哈希Hash、字典树、分成若干小文件+多路归并... 

4:设计实现一个管理内存的小模块,接口为void* checkout(size_t size), void checkin(void* ptr)。

5: 设计一个数据结构,存储一副象棋子的摆放,尽量压缩空间,使得方便通过传输到另外一台机子上然后恢复棋盘。

6:数组的众数问题,最长递增子序列问题。找大量数据中前k个大的数。找大量数据中第k大的数。

7:一个平面中有很多点,用最快的算法找出相隔最近的两个点。

8:select/poll和epoll,基本互联网公司都会提到这个东西。

9:给敏感词列表,和一大段文本,考虑一个敏感词过滤的算法。

10:海量数据问题,很多,一般方法就为分治、hash、位图。

很多没有标准答案,面试过程中的探讨很重要。找工作不难,找份好工作还是难的,基础知识很重要,数据结构和算法、操作系统、编程语言的掌握,数据库和网络。可以根据自己的喜好,偏向于某个方向。


转自: http://www.moorekang.com/2010/10/27/forc.html
posted @ 2011-09-22 23:36 simplyzhao 阅读(233) | 评论 (0)编辑 收藏

基本解释

  const是一个C语言的关键字,它限定一个变量不允许被改变。使用const在一定程度上可以提高程序的健壮性,另外,在观看别人代码的时候,清晰理解const所起的作用,对理解对方的程序也有一些帮助。

  虽然这听起来很简单,但实际上,const的使用也是c语言中一个比较微妙的地方,微妙在何处呢?请看下面几个问题。

  问题:const变量 & 常量

  为什么我象下面的例子一样用一个const变量来初始化数组,ANSI C的编译器会报告一个错误呢?

  const int n = 5;

  int a[n];

  答案与分析:

  1)、这个问题讨论的是“常量”与“只读变量”的区别。常量肯定是只读的,例如5, “abc”,等,肯定是只读的,因为程序中根本没有地方存放它的值,当然也就不能够去修改它。而“只读变量”则是在内存中开辟一个地方来存放它的值,只不过这个值由编译器限定不允许被修改。C语言关键字const就是用来限定一个变量不允许被改变的修饰符(Qualifier)。上述代码中变量n被修饰为只读变量,可惜再怎么修饰也不是常量。而ANSI C规定数组定义时维度必须是“常量”,“只读变量”也是不可以的。

  2)、注意:在ANSI C中,这种写法是错误的,因为数组的大小应该是个常量,而const int n,n只是一个变量(常量 != 不可变的变量,但在标准C++中,这样定义的是一个常量,这种写法是对的),实际上,根据编译过程及内存分配来看,这种用法本来就应该是合理的,只是ANSI C对数组的规定限制了它。

  3)、那么,在ANSI C 语言中用什么来定义常量呢?答案是enum类型和#define宏,这两个都可以用来定义常量。

  问题:const变量 & const 限定的内容

  下面的代码编译器会报一个错误,请问,哪一个语句是错误的呢?

  typedef char * pStr;

  char string[4] = "abc";

  const char *p1 = string;

  const pStr p2 = string;

  p1++;

  p2++;

  答案与分析:

  问题出在p2++上。

  1)、const使用的基本形式: const char m;

  限定m不可变。

  2)、替换1式中的m, const char *pm;

  限定*pm不可变,当然pm是可变的,因此问题中p1++是对的。

  3)、替换1式char, const newType m;

  限定m不可变,问题中的charptr就是一种新类型,因此问题中p2不可变,p2++是错误的。

  问题:const变量 & 字符串常量

  请问下面的代码有什么问题?

  char *p = "i'm hungry!";

  p[0]= 'I';

  答案与分析:

  上面的代码可能会造成内存的非法写操作。分析如下, “i'm hungry”实质上是字符串常量,而常量往往被编译器放在只读的内存区,不可写。p初始指向这个只读的内存区,而p[0] = 'I'则企图去写这个地方,编译器当然不会答应。

  问题:const变量 & 字符串常量2

  请问char a[3] = "abc" 合法吗?使用它有什么隐患?

  答案与分析:

  在标准C中这是合法的,但是它的生存环境非常狭小;它定义一个大小为3的数组,初始化为“abc”,,注意,它没有通常的字符串终止符'\0',因此这个数组只是看起来像C语言中的字符串,实质上却不是,因此所有对字符串进行处理的函数,比如strcpy、printf等,都不能够被使用在这个假字符串上。

  问题:const & 指针

  类型声明中const用来修饰一个常量,有如下两种写法,那么,请问,下面分别用const限定不可变的内容是什么?

  1)、const在前面

  const int nValue; //nValue是const

  const char *pContent; //*pContent是const, pContent可变

  const (char *) pContent;//pContent是const,*pContent可变

  char* const pContent; //pContent是const,*pContent可变

  const char* const pContent; //pContent和*pContent都是const

  2)、const在后面,与上面的声明对等

  int const nValue; // nValue是const

  char const * pContent;// *pContent是const, pContent可变

  (char *) const pContent;//pContent是const,*pContent可变

  char* const pContent;// pContent是const,*pContent可变

  char const* const pContent;// pContent和*pContent都是const

  答案与分析:

  const和指针一起使用是C语言中一个很常见的困惑之处,在实际开发中,特别是在看别人代码的时候,常常会因为这样而不好判断作者的意图,下面讲一下我的判断原则:

  沿着*号划一条线,const和谁在一边,那么谁就是const,即const限定的元素就是它。你可以根据这个规则来看上面声明的实际意义,相信定会一目了然。

  另外,需要注意:对于const (char *) ; 因为char *是一个整体,相当于一个类型(如 char),因此,这是限定指针是const。

posted @ 2011-09-21 15:00 simplyzhao 阅读(161) | 评论 (0)编辑 收藏

1. 用预处理指令#define 声明一个常数,用以表明1年中有多少秒(忽略闰年问题)

#define SECONDS_PER_YEAR (60 * 60 * 24 * 365)UL
我在这想看到几件事情:
1). #define 语法的基本知识(例如:不能以分号结束,括号的使用,等等)
2). 懂得预处理器将为你计算常数表达式的值,因此,直接写出你是如何计算一年中有多少秒而不是计算出实际的值,是更清晰而没有代价的。
3). 意识到这个表达式将使一个16位机的整型数溢出-因此要用到长整型符号L,告诉编译器这个常数是的长整型数。
4). 如果你在你的表达式中用到UL(表示无符号长整型),那么你有了一个好的起点。记住,第一印象很重要。

2. 写一个“标准”宏MIN,这个宏输入两个参数并返回较小的一个。

#define MIN(A,B) ((A) <= (B) ?(A) : (B))
这个测试是为下面的目的而设的:
1). 标识#define在宏中应用的基本知识。这是很重要的,因为直到嵌入(inline)操作符变为标准C的一部分,宏是方便产生嵌入代码的唯一方法,
对于嵌入式系统来说,为了能达到要求的性能,嵌入代码经常是必须的方法。
2). 三重条件操作符的知识。这个操作符存在C语言中的原因是它使得编译器能产生比if-then-else更优化的代码,了解这个用法是很重要的。
3). 懂得在宏中小心地把参数用括号括起来
4). 我也用这个问题开始讨论宏的副作用,例如:当你写下面的代码时会发生什么事?
least = MIN(*p++, b);

3. 预处理器标识#error的目的是什么?

如果你不知道答案,请看参考文献1。这问题对区分一个正常的伙计和一个书呆子是很有用的。只有书呆子才会读C语言课本的附录去找出象这种
问题的答案。当然如果你不是在找一个书呆子,那么应试者最好希望自己不要知道答案。

死循环(Infinite loops)

4. 嵌入式系统中经常要用到无限循环,你怎么样用C编写死循环呢?

这个问题用几个解决方案。我首选的方案是:
while(1)
{
}
一些程序员更喜欢如下方案:
for(;;)
{
}
这个实现方式让我为难,因为这个语法没有确切表达到底怎么回事。如果一个应试者给出这个作为方案,我将用这个作为一个机会去探究他们这样做的
基本原理。如果他们的基本答案是:“我被教着这样做,但从没有想到过为什么。”这会给我留下一个坏印象。
第三个方案是用 goto
Loop:
...
goto Loop;
应试者如给出上面的方案,这说明或者他是一个汇编语言程序员(这也许是好事)或者他是一个想进入新领域的BASIC/FORTRAN程序员。

数据声明(Data declarations)

5. 用变量a给出下面的定义
a) 一个整型数(An integer)
b) 一个指向整型数的指针(A pointer to an integer)
c) 一个指向指针的的指针,它指向的指针是指向一个整型数(A pointer to a pointer to an integer)
d) 一个有10个整型数的数组(An array of 10 integers)
e) 一个有10个指针的数组,该指针是指向一个整型数的(An array of 10 pointers to integers)
f) 一个指向有10个整型数数组的指针(A pointer to an array of 10 integers)
g) 一个指向函数的指针,该函数有一个整型参数并返回一个整型数(A pointer to a function that takes an integer as an argument and returns an integer)
h) 一个有10个指针的数组,该指针指向一个函数,该函数有一个整型参数并返回一个整型数( An array of ten pointers to functions that take an integer
argument and return an integer )

答案是:
a) int a; // An integer
b) int *a; // A pointer to an integer
c) int **a; // A pointer to a pointer to an integer
d) int a[10]; // An array of 10 integers
e) int *a[10]; // An array of 10 pointers to integers
f) int (*a)[10]; // A pointer to an array of 10 integers
g) int (*a)(int); // A pointer to a function a that takes an integer argument and returns an integer
h) int (*a[10])(int); // An array of 10 pointers to functions that take an integer argument and return an integer

人们经常声称这里有几个问题是那种要翻一下书才能回答的问题,我同意这种说法。当我写这篇文章时,为了确定语法的正确性,我的确查了一下书。
但是当我被面试的时候,我期望被问到这个问题(或者相近的问题)。因为在被面试的这段时间里,我确定我知道这个问题的答案。应试者如果不知道
所有的答案(或至少大部分答案),那么也就没有为这次面试做准备,如果该面试者没有为这次面试做准备,那么他又能为什么出准备呢?

Static

6. 关键字static的作用是什么?

这个简单的问题很少有人能回答完全。在C语言中,关键字static有三个明显的作用:
1). 在函数体,一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
2). 在模块内(但在函数体外),一个被声明为静态的变量可以被模块内所用函数访问,但不能被模块外其它函数访问。它是一个本地的全局变量。
3). 在模块内,一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是,这个函数被限制在声明它的模块的本地范围内使用。
大多数应试者能正确回答第一部分,一部分能正确回答第二部分,同是很少的人能懂得第三部分。这是一个应试者的严重的缺点,因为他显然不懂得本地化数
据和代码范围的好处和重要性。

Const

7.关键字const是什么含意?
我只要一听到被面试者说:“const意味着常数”,我就知道我正在和一个业余者打交道。去年Dan Saks已经在他的文章里完全概括了const的所有用法,因此ESP(译者:Embedded Systems Programming)的每一位读者应该非常熟悉const能做什么和不能做什么.如果你从没有读到那篇文章,只要能说出const意味着“只读”就可以了。尽管这个答案不是完全的答案,但我接受它作为一个正确的答案。(如果你想知道更详细的答案,仔细读一下Saks的文章吧。)如果应试者能正确回答这个问题,我将问他一个附加的问题:下面的声明都是什么意思?

const int a;
int const a;
const int *a;
int * const a;
int const * a const;

前两个的作用是一样,a是一个常整型数。第三个意味着a是一个指向常整型数的指针(也就是,整型数是不可修改的,但指针可以)。第四个意思a是一个指向整型数的常指针(也就是说,指针指向的整型数是可以修改的,但指针是不可修改的)。最后一个意味着a是一个指向常整型数的常指针(也就是说,指针指向的整型数是不可修改的,同时指针也是不可修改的)。如果应试者能正确回答这些问题,那么他就给我留下了一个好印象。顺带提一句,也许你可能会问,即使不用关键字 const,也还是能很容易写出功能正确的程序,那么我为什么还要如此看重关键字const呢?我也如下的几下理由:
1). 关键字const的作用是为给读你代码的人传达非常有用的信息,实际上,声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾,你就会很快学会感谢这点多余的信息。(当然,懂得用const的程序员很少会留下的垃圾让别人来清理的。)
2). 通过给优化器一些附加的信息,使用关键字const也许能产生更紧凑的代码。
3). 合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数,防止其被无意的代码修改。简而言之,这样可以减少bug的出现。

Volatile

8. 关键字volatile有什么含意 并给出三个不同的例子。

一个定义为volatile的变量是说这变量可能会被意想不到地改变,这样,编译器就不会去假设这个变量的值了。精确地说就是,优化器在用到这个变量时必须每次都小心地重新读取这个变量的值,而不是使用保存在寄存器里的备份。下面是volatile变量的几个例子:
1). 并行设备的硬件寄存器(如:状态寄存器)
2). 一个中断服务子程序中会访问到的非自动变量(Non-automatic variables)
3). 多线程应用中被几个任务共享的变量
回答不出这个问题的人是不会被雇佣的。我认为这是区分C程序员和嵌入式系统程序员的最基本的问题。嵌入式系统程序员经常同硬件、中断、RTOS等等打交道,所用这些都要求volatile变量。不懂得volatile内容将会带来灾难。
假设被面试者正确地回答了这是问题(嗯,怀疑这否会是这样),我将稍微深究一下,看一下这家伙是不是直正懂得volatile完全的重要性。
1). 一个参数既可以是const还可以是volatile吗?解释为什么。
2). 一个指针可以是volatile 吗?解释为什么。
3). 下面的函数有什么错误:
int square(volatile int *ptr)
{
return *ptr * *ptr;
}
下面是答案:
1). 是的。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。
2). 是的。尽管这并不很常见。一个例子是当一个中服务子程序修该一个指向一个buffer的指针时。
3). 这段代码的有个恶作剧。这段代码的目的是用来返指针*ptr指向值的平方,但是,由于*ptr指向一个volatile型参数,编译器将产生类似下面的代码:
int square(volatile int *ptr)
{
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由于*ptr的值可能被意想不到地该变,因此a和b可能是不同的。结果,这段代码可能返不是你所期望的平方值!正确的代码如下:
long square(volatile int *ptr)
{
int a;
a = *ptr;
return a * a;
}

位操作(Bit manipulation)

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

对这个问题有三种基本的反应
1). 不知道如何下手。该被面者从没做过任何嵌入式系统的工作。
2). 用bit fields。Bit fields是被扔到C语言死角的东西,它保证你的代码在不同编译器之间是不可移植的,同时也保证了的你的代码是不可重用的。我最近不幸看到 Infineon为其较复杂的通信芯片写的驱动程序,它用到了bit fields因此完全对我无用,因为我的编译器用其它的方式来实现bit fields的。从道德讲:永远不要让一个非嵌入式的家伙粘实际硬件的边。
3). 用 #defines 和 bit masks 操作。这是一个有极高可移植性的方法,是应该被用到的方法。最佳的解决方案如下:
#define BIT3 (0x1<<3)
static int a;
void set_bit3(void)
{
a |= BIT3;
}
void clear_bit3(void)
{
a &= ~BIT3;
}
一些人喜欢为设置和清除值而定义一个掩码同时定义一些说明常数,这也是可以接受的。我希望看到几个要点:说明常数、|=和&=~操作。

访问固定的内存位置(Accessing fixed memory locations)

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

这一问题测试你是否知道为了访问一绝对地址把一个整型数强制转换(typecast)为一指针是合法的。这一问题的实现方式随着个人风格不同而不同。典型的类似代码如下:
int *ptr;
ptr = (int *)0x67a9;
*ptr = 0xaa55;

一个较晦涩的方法是:
*(int * const)(0x67a9) = 0xaa55;

即使你的品味更接近第二种方案,但我建议你在面试时使用第一种方案。

中断(Interrupts)

11. 中断是嵌入式系统中重要的组成部分,这导致了很多编译开发商提供一种扩展—让标准C支持中断。具代表事实是,产生了一个新的关键字 __interrupt。下面的代码就使用了__interrupt关键字去定义了一个中断服务子程序(ISR),请评论一下这段代码的。

__interrupt double compute_area (double radius)
{
double area = PI * radius * radius;
printf(" Area = %f", area);
return area;
}

这个函数有太多的错误了,以至让人不知从何说起了:
1). ISR 不能返回一个值。如果你不懂这个,那么你不会被雇用的。
2). ISR 不能传递参数。如果你没有看到这一点,你被雇用的机会等同第一项。
3). 在许多的处理器/编译器中,浮点一般都是不可重入的。有些处理器/编译器需要让额处的寄存器入栈,有些处理器/编译器就是不允许在ISR中做浮点运算。此外,ISR应该是短而有效率的,在ISR中做浮点运算是不明智的。
4). 与第三点一脉相承,printf()经常有重入和性能上的问题。如果你丢掉了第三和第四点,我不会太为难你的。不用说,如果你能得到后两点,那么你的被雇用前景越来越光明了。

代码例子(Code examples)

12 . 下面的代码输出是什么,为什么?

void foo(void)
{
unsigned int a = 6;
int b = -20;
(a+b > 6) puts("> 6") : puts("<= 6");
}


这个问题测试你是否懂得C语言中的整数自动转换原则,我发现有些开发者懂得极少这些东西。不管如何,这无符号整型问题的答案是输出是“>6”。原因是当表达式中存在有符号类型和无符号类型时所有的操作数都自动转换为无符号类型。因此-20变成了一个非常大的正整数,所以该表达式计算出的结果大于6。这一点对于应当频繁用到无符号数据类型的嵌入式系统来说是丰常重要的。如果你答错了这个问题,你也就到了得不到这份工作的边缘。

13. 评价下面的代码片断:

unsigned int zero = 0;
unsigned int compzero = 0xFFFF;
/*1's complement of zero */

对于一个int型不是16位的处理器为说,上面的代码是不正确的。应编写如下:

unsigned int compzero = ~0;

这一问题真正能揭露出应试者是否懂得处理器字长的重要性。在我的经验里,好的嵌入式程序员非常准确地明白硬件的细节和它的局限,然而PC机程序往往把硬件作为一个无法避免的烦恼。
到了这个阶段,应试者或者完全垂头丧气了或者信心满满志在必得。如果显然应试者不是很好,那么这个测试就在这里结束了。但如果显然应试者做得不错,那么我就扔出下面的追加问题,这些问题是比较难的,我想仅仅非常优秀的应试者能做得不错。提出这些问题,我希望更多看到应试者应付问题的方法,而不是答案。不管如何,你就当是这个娱乐吧…

动态内存分配(Dynamic memory allocation)

14. 尽管不像非嵌入式计算机那么常见,嵌入式系统还是有从堆(heap)中动态分配内存的过程的。那么嵌入式系统中,动态分配内存可能发生的问题是什么?

这里,我期望应试者能提到内存碎片,碎片收集的问题,变量的持行时间等等。这个主题已经在ESP杂志中被广泛地讨论过了(主要是 P.J. Plauger, 他的解释远远超过我这里能提到的任何解释),所有回过头看一下这些杂志吧!让应试者进入一种虚假的安全感觉后,我拿出这么一个小节目:下面的代码片段的输出是什么,为什么?

char *ptr;
if ((ptr = (char *)malloc(0)) == NULL)
puts("Got a null pointer");
else
puts("Got a valid pointer");

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

Typedef

15. Typedef 在C语言中频繁用以声明一个已经存在的数据类型的同义字。也可以用预处理器做类似的事。例如,思考一下下面的例子:
#define dPS struct s *
typedef struct s * tPS;

以上两种情况的意图都是要定义dPS 和 tPS 作为一个指向结构s指针。哪种方法更好呢?(如果有的话)为什么?


这是一个非常微妙的问题,任何人答对这个问题(正当的原因)是应当被恭喜的。答案是:typedef更好。思考下面的例子:
dPS p1,p2;
tPS p3,p4;

第一个扩展为
struct s * p1, p2;

上面的代码定义p1为一个指向结构的指,p2为一个实际的结构,这也许不是你想要的。第二个例子正确地定义了p3 和p4 两个指针。

晦涩的语法

16. C语言同意一些令人震惊的结构,下面的结构是合法的吗,如果是它做些什么?
int a = 5, b = 7, c;
c = a+++b;

这个问题将做为这个测验的一个愉快的结尾。不管你相不相信,上面的例子是完全合乎语法的。问题是编译器如何处理它?水平不高的编译作者实际上会争论这个问题,根据最处理原则,编译器应当能处理尽可能所有合法的用法。因此,上面的代码被处理成:
c = a++ + b;
因此, 这段代码持行后a = 6, b = 7, c = 12。
如果你知道答案,或猜出正确答案,做得好。如果你不知道答案,我也不把这个当作问题。我发现这个问题的最大好处是:这是一个关于代码编写风格,代码的可读性,代码的可修改性的好的话题

posted @ 2011-09-21 14:57 simplyzhao 阅读(174) | 评论 (0)编辑 收藏
大端模式与小端模式
一、概念及详解
  在各种体系的计算机中通常采用的字节存储机制主要有两种: big-endian和little-endian,即大端模式和小端模式。
  先回顾两个关键词,MSB和LSB:
  MSB:Most Significant Bit ------- 最高有效位
        LSB:Least Significant Bit ------- 最低有效位
  大端模式(big-edian)
  big-endian:MSB存放在最低端的地址上。
  举例,双字节数0x1234以big-endian的方式存在起始地址0x00002000中:
        | data |<-- address
        | 0x12 |<-- 0x00002000
        | 0x34 |<-- 0x00002001
  在Big-Endian中,对于bit序列中的序号编排方式如下(以双字节数0x8B8A为例):
        bit | 0 1 2 3 4 5 6 7 | 8 9 10 11 12 13 14 15
        ------MSB----------------------------------LSB
        val | 1 0 0 0 1 0 1 1 | 1 0 0 0 1 0 1 0 |
        +--------------------------------------------+
        = 0x8 B 8 A
  小端模式(little-endian)
  little-endian:LSB存放在最低端的地址上。
  举例,双字节数0x1234以little-endian的方式存在起始地址0x00002000中:
| data |<-- address
        | 0x34 |<-- 0x00002000
        | 0x12 |<-- 0x00002001
  在Little-Endian中,对于bit序列中的序号编排和Big-Endian刚好相反,其方式如下(以双字节数0x8B8A为例):
bit | 15 14 13 12 11 10 9 8 | 7 6 5 4 3 2 1 0
        ------MSB-----------------------------------LSB
        val | 1 0 0 0 1 0 1 1 | 1 0 0 0 1 0 1 0 |
        +---------------------------------------------+
        = 0x8 B 8 A 
二、数组在大端小端情况下的存储:
  以unsigned int value = 0x12345678为例,分别看看在两种字节序下其存储情况,我们可以用unsigned char buf[4]来表示value:
  Big-Endian: 低地址存放高位,如下:
       高地址
        ---------------
        buf[3] (0x78) -- 低位
        buf[2] (0x56)
        buf[1] (0x34)
        buf[0] (0x12) -- 高位
        ---------------
        低地址
Little-Endian: 低地址存放低位,如下:
        高地址
        ---------------
        buf[3] (0x12) -- 高位
        buf[2] (0x34)
        buf[1] (0x56)
        buf[0] (0x78) -- 低位
        --------------
        低地址

  三、大端小端转换方法:
  Big-Endian转换成Little-Endian如下:
#define BigtoLittle16(A)                 ((((uint16)(A) & 0xff00) >> 8) | \
                                                          (((uint16)(A) & 0x00ff) << 8))
#define BigtoLittle32(A)                 ((((uint32)(A) & 0xff000000) >> 24) | \
                                                          (((uint32)(A) & 0x00ff0000) >> 8) | \
                                                          (((uint32)(A) & 0x0000ff00) << 8) | \
                                                          (((uint32)(A) & 0x000000ff) << 24))

  四、大端小端检测方法:
  如何检查处理器是big-endian还是little-endian?
  联合体union的存放顺序是所有成员都从低地址开始存放,利用该特性就可以轻松地获得了CPU对内存采用Little-endian还是Big-endian模式读写。
int checkCPUendian()
{
union
{
unsigned int a;
unsigned char b;
}c;
c.a = 1;
return (c.b == 1);
}
/*return 1 : little-endian, return 0:big-endian*/ 

网络字节顺序

1、字节内的比特位不受这种顺序的影响
比如一个字节 1000 0000 (或表示为十六进制 80H)不管是什么顺序其内存中的表示法都是这样。
2、大于1个字节的数据类型才有字节顺序问题
比如 Byte A,这个变量只有一个字节的长度,所以根据上一条没有字节顺序问题。所以字节顺序是“字节之间的相对顺序”的意思。
3、大于1个字节的数据类型的字节顺序有两种
比如 short B,这是一个两字节的数据类型,这时就有字节之间的相对顺序问题了。
网络字节顺序是“所见即所得”的顺序。而Intel类型的CPU的字节顺序与此相反。
比如上面的 short B=0102H(十六进制,每两位表示一个字节的宽度)。所见到的是“0102”,按一般数学常识,数轴从左到右的方向增加,即内存地址从左到右增加的话,在内存中这个 short B的字节顺序是:
01 02
这就是网络字节顺序。所见到的顺序和在内存中的顺序是一致的!
而相反的字节顺序就不同了,其在内存中的顺序为:02 01
假设通过抓包得到网络数据的两个字节流为:01 02
如果这表示两个 Byte类型的变量,那么自然不需要考虑字节顺序的问题。
如果这表示一个 short 变量,那么就需要考虑字节顺序问题。根据网络字节顺序“所见即所得”的规则,这个变量的值就是:0102
假设本地主机是Intel类型的,那么要表示这个变量,有点麻烦:
定义变量 short X,
字节流地址为:pt,按顺序读取内存是为
x=*((short*)pt);
那么X的内存顺序当然是 01 02
按非“所见即所得”的规则,这个内存顺序和看到的一样显然是不对的,所以要把这两个字节的位置调换。
调换的方法可以自己定义,但用已经有的API还是更为方便。

网络字节顺序与主机字节顺序
NBO与HBO 网络字节顺序NBO(Network Byte Order):按从高到低的顺序存储,在网络上使用统一的网络字节顺序,可以避免兼容性问题。主机字节顺序(HBO,Host Byte Order):不同的机器HBO不相同,与CPU设计有关计算机数据存储有两种字节优先顺序:高位字节优先和低位字节优先。Internet上数据以高位字节优先顺序在网络上传输,所以对于在内部是以低位字节优先方式存储数据的机器,在Internet上传输数据时就需要进行转换。 

htonl()
简述:
    将主机的无符号长整形数转换成网络字节顺序。
    #include <winsock.h>
    u_long PASCAL FAR htonl( u_long hostlong);
    hostlong:主机字节顺序表达的32位数。
注释:
    本函数将一个32位数从主机字节顺序转换成网络字节顺序。
返回值:
    htonl()返回一个网络字节顺序的值。

inet_ntoa()
简述:
将网络地址转换成“.”点隔的字符串格式。
#include <winsock.h>
char FAR* PASCAL FAR inet_ntoa( struct in_addr in);
in:一个表示Internet主机地址的结构。
注释:
本函数将一个用in参数所表示的Internet地址结构转换成以“.” 间隔的诸如“a.b.c.d”的字符串形式。请注意inet_ntoa()返回的字符串存放在WINDOWS套接口实现所分配的内存中。应用程序不应假设该内存是如何分配的。在同一个线程的下一个WINDOWS套接口调用前,数据将保证是有效。
返回值:
若无错误发生,inet_ntoa()返回一个字符指针。否则的话,返回NULL。其中的数据应在下一个WINDOWS套接口调用前复制出来。

网络中传输的数据有的和本地字节存储顺序一致,而有的则截然不同,为了数据的一致性,就要把本地的数据转换成网络上使用的格式,然后发送出去,接收的时候也是一样的,经过转换然后才去使用这些数据,基本的库函数中提供了这样的可以进行字节转换的函数,如和htons( ) htonl( ) ntohs( ) ntohl( ),这里n表示network,h表示host,htons( ) htonl( )用于本地字节向网络字节转换的场合,s表示short,即对2字节操作,l表示long即对4字节操作。同样ntohs( )ntohl( )用于网络字节向本地格式转换的场合。
posted @ 2011-09-21 13:03 simplyzhao 阅读(224) | 评论 (0)编辑 收藏

原文在http://hi.baidu.com/deep_pro/blog/item/cf964b0ade9f4d1594ca6b1b.html

这些词之间的区别难倒了很多人,还有什么同步阻塞, 同步非阻塞, 异步阻塞, 异步非阻塞,乱七八糟的。
很多文章也想讲明白这个问题。著名且引起热议的有

http://www.ibm.com/developerworks/cn/linux/l-async/

http://www.cppblog.com/converse/archive/2009/05/13/82879.html

可是看了之后还是有点将信将疑,跑到图书馆翻了UNP 第一卷,不愧是圣经级别的著作,似有所悟。
UNP所述:
POSIX定义中,同步IO操作:IO操作将导致请求进程阻塞,直到IO操作完成。
异步IO操作:IO操作不导致请求进程阻塞

UNP中总结的IO模型有5种之多
阻塞IO,非阻塞IO,IO复用,信号驱动IO,异步IO,前四种都属于同步IO。

阻塞IO不必说了
非阻塞IO ,IO请求时加上O_NONBLOCK一类的标志位,立刻返回,IO没有就绪会返回错误,需要请求进程主动轮询不断发IO请求直到返回正确
IO复用同非阻塞IO本质一样,不过利用了新的select系统调用,由内核来负责本来是请求进程该做的轮询操作。看似比非阻塞IO还多了一个系统调用开销,不过因为可以支持多路IO,才算提高了效率
信号驱动IO,调用sigaltion系统调用,当内核中IO数据就绪时以SIGIO信号通知请求进程,请求进程再把数据从内核读入到用户空间,这一步是阻塞的。
异步IO,如定义所说,不会因为IO操作阻塞,IO操作全部完成才通知请求进程。

这样以来,同步和阻塞,异步和非阻塞就不会被混淆了,它们不是同一个方面上的概念,不能比较区别

同步和异步是只跟IO操作过程中进程的状态变化有关
阻塞和非阻塞就是进程的两种状态。

posted @ 2011-09-09 17:03 simplyzhao 阅读(244) | 评论 (0)编辑 收藏
     摘要: C++ 虚函数表解析 陈皓http://blog.csdn.net/haoel  前言 C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。所谓泛型技术,说白了就是试图使用不变...  阅读全文
posted @ 2011-09-07 19:22 simplyzhao 阅读(226) | 评论 (0)编辑 收藏
     摘要: epoll方法实现non-blocking socketPosted on 2011/06/17 by Min© Min的技术分享 – 54min.com (RSS订阅) | 原文链接:http://54min.com/post/using-epoll-method-create-non-blocking-socket.htm...  阅读全文
posted @ 2011-09-05 20:00 simplyzhao 阅读(4631) | 评论 (0)编辑 收藏
     摘要: HTTP protocolPosted on 2011/05/02 by Min© Min的技术分享 – 54min.com (RSS订阅) | 原文链接:http://54min.com/post/the-http-protocol.htmlHTTP protocolHTTP是应用层协议(传输层采用TCP因此是面向连接的),...  阅读全文
posted @ 2011-09-04 22:19 simplyzhao 阅读(385) | 评论 (0)编辑 收藏
问题:
写一个函数 unsigned RevBit(unsigned val);

unsigned x = RevBit(0xf0ec9999);
x应该为 0x9999370f。

0xf0ec9999 == 11110000111011001001100110011001(二进制)

0x9999370f == 10011001100110010011011100001111(二进制)


思路:相邻两位互调位置(即一位换一位),再相邻的两位换两位,在相邻的四位与四位互调位置,再八位与八位互调位置,最后前十六位和后十六位互换位置,完成32位整数逆转。思路与归并排序相似。

代码:
#include <stdio.h>;
 
unsigned RevBit(unsigned x)
{
x
=(x&0x55555555)<<1|(x>>1)&0x55555555;
x
=(x&0x33333333)<<2|(x>>2)&0x33333333;
x
=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
x
=(x&0x00ff00ff)<<8|(x>>8)&0x00ff00ff;
x
=x<<16|x>>16;
return x;
}
 
int main()
{
unsigned x 
= RevBit(0xf0ec9999);
printf(
"%x\n",x);
return 0;
}

更多解法: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
posted @ 2011-09-04 16:03 simplyzhao 阅读(333) | 评论 (0)编辑 收藏

题目

  1. 给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
  2. 给你n个数,其中有且仅有两个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

答案

  1. 从头到尾异或一遍,最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质:两次异或同一个数,结果不变。再考虑到异或运算满足交换律,先异或和后异或都是一样的,因此这个算法显然正确。

  2. 从头到尾异或一遍,你就得到了需要求的两个数异或后的值。这两个数显然不相等,异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位,然后把所有这n个数分成两类,在那一位上是0的分成一类,在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

posted @ 2011-09-04 15:37 simplyzhao 阅读(216) | 评论 (0)编辑 收藏
仅列出标题
共21页: 1 2 3 4 5 6 7 8 9 Last 

导航

<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜