- 编译C语言源文件为可执行文件经过的步骤
- 小端法与大端法
- 机器实际执行的程序只是对一系列指令进行编码的字节序列
- new、delete与malloc、free之间的联系和区别
- 为什么不建议让异常离开析构函数？
- 使用define定义一年有多少毫秒
- 使用define定义max函数
- 关键字volatile的意义及使用场景
- 避免同一头文件的多次include
- 字节对齐理解
- 对一个包含虚函数成员的对象bzero()会有什么问题？
- 常量存储器与栈空间
- 异或操作总结
int *p[5]和int (*p)[5]的区别- 用C++实现一个不能被继承的类
- 判断结构体大小
- 虚函数和纯虚函数的区别
- 虚基类成员的可见性
- 不能使用宏开始或者结束注释
- C++中模板的编译过程
- C++局部变量，全局变量，静态变量的作用域，生命期
- char的整型运算
- define中为何经常会使用 do{…}while(0);来包装多条语句代码
- define的一些注意点
- static、const、volatile、typeof关键字的用途描述
- std::vector实现原理及特定场景下的改进
- STL中的stable_sort()的时间复杂度是多少
- 机器代码对有条件执行指令的支持方式
- 条件传送指令
- 过程（函数）调用的机器级实现
- Y86指令集体系结构
- 循环展开
- 处理器预测错误处罚
- 编写高速缓存友好的代码
- 高速缓存对程序性能的影响
- 目标文件的形式
- 如果i=5；那么 a=(++i)–;之后，a和i的值各是多少
- 多态类中的虚函数表是Compile-Time，还是Run-Time时建立的?
- strcpy,memcpy,sprintf的区别及前两个函数的实现
- 从N个数中挑选出最小的m个数。N很大，比如100万个，但是可以一次加载到内存
- 任意挑选一种JVM，描述垃圾回收的实现机制。
- 如何实现一个getElementsByClassName(dom, className)方法，以获得所有包含某一个className的所有dom结点
- 如何实现一个JSON对象的拷贝
- 请说明JAVA不需要程序员回收内存的保障机制。请列举2~~3个JAVA的垃圾回收机制算法，说明基本思想和主要优缺点。
编译C语言源文件为可执行文件经过的步骤
执行gcc -o hello hello.c，完成从C语言代码到可执行文件的整个过程分为以下4个阶段：
hello.c源程序（文本）
-> 预处理器（cpp） -> hello.i被修改的源程序（文本）
-> 编译器（ccl） -> hello.s汇编程序（文本）
-> 汇编器（as） -> hello.o可重定位目标程序（二进制）
-> 链接器（ld） -> hello可执行目标程序（二进制）
执行：
gcc -O1 -o p p1.c p2.c
其中-O1指使用第一级优化。gcc会调用一系列程序来将源代码转化为可执行代码：
- 首先C预处理器扩展源代码，插入所有用#include指定的文件，并扩展所有用#define定义的宏；
- 然后编译器产生两个源代码的汇编代码:p1.s和p2.s；
- 接着汇编器将汇编代码转化为二进制目标代码：p1.o和p2.o，目标代码是机器代码的一种形式，它包含所有指令的二进制表示，但是还没有填入地址的全局值；
- 最后，链接器将两个目标代码文件与实现库函数的代码合并，并产生最终的可执行文件p。
小端法与大端法
计算机使用字节（8位的块）作为最小的可寻址的存储单位，而不是在存储器中访问单独的位。存储器的每个字节都由一个唯一的数字来标识，称为它的地址。 对于跨越多字节的程序对象必须建立两个规则：这个对象的地址是什么，以及在存储器中如何排列这些字节。最低有效字节在最前面的方式称为小端法，最高有效字节在最前面的方式称为大端法。假设变量x的类型为int，位于地址0x100处，它的16进制值为0x01234567，地址范围为0x100~0x103字节，其排列顺序可能如下：
0x100 0x101 0x102 0x103
01 23 45 67 大端法
67 45 23 01 小端法
在不同类型的机器之间传送数据时，字节的顺序会称为问题。
机器实际执行的程序只是对一系列指令进行编码的字节序列
编译器会将C语言提供的相对比较抽象的执行模型表示的程序转化为处理器执行的非常基本的指令，即汇编代码。汇编代码的表示非常接近于机器代码，如下C语言代码：
int accum = 0 ;
int sum(int x, int y){
int t = x + y;
accum += t;
return t;
}
执行gcc -O1 -S code.c将产生一个如下内容的code.s文件：
sum:
pushl %ebp
movl %esp,%ebp
movl 12(%ebp),%eax
addl 8(%ebp),%eax
addl %eax,accum
popl %ebp
ret
这段代码中已经去除了所有关于局部变量名或数据类型的信息，且代码中有一个对全局变量accum的引用，这是因为编译器还不能确定这个变量会放在存储器中的哪个位置。 如果使用gcc -O1 -c code.c，将生产一个目标文件code.o，它是一个二进制文件，在文件中可以找到一段字节序列：
55 89 e5 8b 45 0c 03 45 08 01 05 00 00 00 00 5d c3
这段字节序列就是上面汇编代码对应的目标代码，由此可见机器实际执行的程序只是对一系列指令进行编码的字节序列。
在Linux上可以使用反汇编器objdump来生成目标代码对应的字节序列：
objdump -d code.o
生成结果如下：
00000000 <sum>:
0:55 pushl %ebp
1:89 e5 movl %esp,%ebp
3:8b 45 0c movl 12(%ebp),%eax
6:03 45 08 addl 8(%ebp),%eax
9:01 05 00 00 00 00 addl %eax,accum
f:5d popl %ebp
10:c3 ret
生成实际可执行的代码需要对一组目标代码文件运行链接器，这一组目标代码文件中必须含有一个main函数。链接器将代码的地址移到一段地址范围中，且会确定全局变量的地址：
08048394 <sum>:
8048394:55 pushl %ebp
8048395:89 e5 movl %esp,%ebp
8048397:8b 45 0c movl 12(%ebp),%eax
804839a:03 45 08 addl 8(%ebp),%eax
804839d:01 05 00 00 00 00 addl %eax,0x804a018
80483a3:5d popl %ebp
80483a4:c3 ret
最终链接后生成的文件会比较大，是因为它不仅包含了多个文件的代码，还包含了用来启动和终止程序的信息，以及用来与操作系统交互的信息。
new、delete与malloc、free之间的联系和区别
malloc/free和new/delete的联系
-
- 存储方式相同。malloc和new动态申请的内存都位于堆中。申请的内存都不能自动被操作系统收回，都需要配套的free和delete来释放。
-
- 除了带有构造函数和析构函数的类等数据类型以外，对于一般数据类型，如int、char等等，两组动态申请的方式可以通用，作用效果一样，只是形式不一样。
-
- 内存泄漏对于malloc或者new都是可以检查出来的，区别在于new可以指明是哪个文件的哪一行，而malloc没有这些信息。
-
- 两组都需要配对使用，malloc配free，new配delete。在C++中，两组之间不能混着用（虽说有时能编译过，但容易存在较大的隐患）。
malloc/free和new/delete的区别
-
- malloc返回void类型指针，free的形参为void指针，new和delete直接带具体类型的指针。
-
- malloc和free属于C语言中的函数，需要库的支持，而new/delete是C++中的运算符，况且可以重载，所以new/delete的执行效率高些。
-
- 在C++中，new是类型安全的，而malloc不是。例如：
// 编译时指出错误
int* p = new char[10];
//对数组需要加中括号“[]”
delete [] p;
// 编译时无法指出错误
int* p = malloc(sizeof(char)*10);
//只需要所释放内存的头指针（free释放malloc分配的数组）。在malloc和free的面前没有对象没有数组，只有“内存块”。一次malloc分配的东西，一次free一定能回收。至于内存块的大小内存管理会进行记录，这应该是库函数的事。free的真正弊端在于它不会调用析构函数。
free (p);
- 使用new动态申请类对象的内存空间时，类对象的构建要调用构造函数，相当于对内存空间进行了初始化。而malloc动态申请的类对象的内存空间时，不会初始化，也就是说申请的内存空间无法使用，因为类的初始化是由构造函数完成的。
- 不能用malloc和free来完成类对象的动态创建和删除。
calloc、realloc：
void *calloc(int n,int size);
函数返回值为void型指针。如果执行成功，函数从堆上获得size * n的字节空间，并返回该空间的首地址。如果执行失败，函数返回NULL。该函数与malloc函数的一个显著不同时是，calloc函数得到的内存空间是经过初始化的，其内容全为0。calloc函数适合为数组申请空间，可以将size设置为数组元素的空间长度，将n设置为数组的容量。
realloc函数的功能比malloc函数和calloc函数的功能更为丰富，可以实现内存分配和内存释放的功能，其函数声明如下：
void * realloc(void * p,int n);
其中，指针p必须为指向堆内存空间的指针，即由malloc函数、calloc函数或realloc函数分配空间的指针。realloc函数将指针p指向的内存块的大小改变为n字节。如果n小于或等于p之前指向的空间大小，那么。保持原有状态不变。如果n大于原来p之前指向的空间大小，那么，系统将重新为p从堆上分配一块大小为n的内存空间，同时，将原来指向空间的内容依次复制到新的内存空间上，p之前指向的空间被释放。relloc函数分配的空间也是未初始化的。
注意：使用malloc函数，calloc函数和realloc函数分配的内存空间都要使用free函数或指针参数为NULL的realloc函数来释放。
为什么不建议让异常离开析构函数？
程序抛出异常时候，会导致栈展开，局部对象依次析构。如果析构过程中再次抛出异常，程序将会立即中止。
使用define定义一年有多少毫秒
#define MS_OF_YEAR (365*24*60*60*1000)UL
（对于整数溢出的考虑）
使用define定义max函数
#define MAX(a,b) (a)>(b)?(a): (b)
（对于define中()使用的把握） 例：
#define TEST1 a+b
#define TEST2 (a+b)
void main(void)
{
int a, b, c, d;
c = TEST1; //相当于 c = a+b;
d = TEST2; //相当于 d = (a+b);
}
这样写是防止忽略运算符优先级而导致的错误。
关键字volatile的意义及使用场景
volatile告诉编译器不要持有变量的临时拷贝; 场景可抽象为两个线程，线程1和线程2通过某种方式共享一个变量，线程1根据变量状态进行某种操作，但线程2有可能改变变量的值，由于线程1中对变量的值一直保存到寄存器中，就不会发现变量的改变，此时线程1会做出错误的行为，当然，这个问题也可以由锁进行同步，但会有较大的时间消耗，volatile可以较好的解决此问题。
避免同一头文件的多次include
#ifndef … 或者 #pragma once
#pragma once是编译器相关的，就是说即使这个编译系统上有效，但在其他编译系统也不一定可以，不过现在基本上已经是每个编译器都有这个杂注了。
#ifndef，#define，#endif是C/C++语言中的宏定义，通过宏定义避免文件多次编译。所以在所有支持C++语言的编译器上都是有效的，如果写的程序要跨平台，最好使用这种方式。
字节对齐理解
在结构中，编译器为结构的每个成员按其自然边界（alignment）分配空间。各个成员按照它们被声明的顺序在内存中顺序存储，第一个成员的地址和整个结构的地址相同。 为了使CPU能够对变量进行快速的访问，变量的起始地址应该具有某些特性，即所谓的对齐。比如4字节的int型，其起始地址应该位于4字节的边界上，即起始地址能够被4整除。 对于标准数据类型，它的地址只要是它的长度的整数倍就行了，而非标准数据类型按下面的原则对齐：
- 数组：按照基本数据类型对齐，第一个对齐了后面的自然也就对齐了。
- 联合：按其包含的长度最大的数据类型对齐。
-
结构体：结构体中每个数据类型都要对齐。
比如有如下一个结构体：
struct stu{ char sex; int length; char name[10]; }; struct stu my_stu;由于在x86下，GCC默认按4字节对齐，它会在sex后面跟name后面分别填充三个和两个字节使length和整个结构体对齐。于是我们sizeof(my_stu)会得到长度为20，而不是15。
需要字节对齐的根本原因在于CPU访问数据的效率问题。假设上面整型变量的地址不是自然对齐，比如为0x00000002，则CPU如果取它的值的话需要访问两次内存，第一次取从0x00000002-0x00000003的一个short，第二次取从0x00000004-0x00000005的一个short然后组合得到所要的数据，如果变量在0x00000003地址上的话则要访问三次内存，第一次为char，第二次为short，第三次为char，然后组合得到整型数据。而如果变量在自然对齐位置上，则只要一次就可以取出数据。
对一个包含虚函数成员的对象bzero()会有什么问题？
表面现象：虚函数是在类中被声明为virtual的成员函数，当编译器看到通过指针或引用调用此类函数时，对其执行晚绑定，即通过指针（或引用）指向的类的类型信息来决定该函数是哪个类的。 实现机制：编译器对每个包含虚函数的类创建一个表（称为VTABLE）。在V TABLE中，编译器放置特定类的虚函数地址。在每个带有虚函数的类中，编译器置一指针，称为vpointer（缩写为VPTR），指向这个对象的VTABLE。通过基类指针做虚函数调用时（也就是做多态调用时），编译器静态地插入取得这个VPTR，并在VTABLE表中查找函数地址的代码，这样就能调用正确的函数使晚捆绑发生。 对包含虚函数成员的对象bzero会破坏该对象的虚函数表（VTABLE），调用该虚函数时将core。 原型：
extern void bzero（void *s, int n）;
用法：
#include <string.h>
功能：置字节字符串s的前n个字节为零且包括\0。
说明：bzero无返回值，并且使用strings.h头文件，strings.h曾经是posix标准的一部分，但是在POSIX.1-2001标准里面，这些函数被标记为了遗留函数而不推荐使用。在POSIX.1-2008标准里已经没有这些函数了。推荐使用memset替代bzero。
常量存储器与栈空间
在函数体内声明
[1] char *str="abc";
[2] char str[]={'a','b','c'};
有什么区别？
- [1][2] 中str变量都分配在栈上
- [1] 中str指向常量存储区的字符串”abc”，其中字符串末尾会补0
- [2] 中str数组的内容存储于栈空间，数组大小为3，字符串不会补0
异或操作总结
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
1 ^ 1 = 0
0 ^ a = a
代码验证：
int a = 123, b = 456;
a ^ b = 435;
a ^ b ^ a = 456 (b)
a ^ b ^ b = 123 (a)
应用：不用临时变量交换两值：
a = a ^ b
b = b ^ a
a = a ^ b
int *p[5]和int (*p)[5]的区别
前者定义了指针的数组，后者定义了指向数组的指针
用C++实现一个不能被继承的类
将构造函数和析构函数声明为私有函数，该函数就不可被继承。同时为了该类可以被实例化，在类中定义一个静态函数，返回初始化的一个类对象。
判断结构体大小
偏移量
偏移量指的是结构体变量中成员的地址和结构体变量地址的差。结构体大小等于最后一个成员的偏移量加上最后一个成员的大小。 由于存储变量时地址对齐的要求，编译器在编译程序时会遵循两条原则：
- 1.结构体变量中成员的偏移量必须是成员大小的整数倍（0被认为是任何数的整数倍）
- 2.结构体大小必须是所有成员大小的整数倍。
此外：结构体变量的首地址能够被其最宽基本类型成员的大小所整除； 因此不同的定义顺序会影响到结构体的大小：
struct s{
char c;
int i;
char cc;
}; // 大小为12
struct s{
char c;
char cc;
int i;
}; // 大小为8
当结构体中的成员又是另外一种结构体类型时，只需要把其展开，展开后的结构体的第一个成员的偏移量应当是被展开的结构体中最大的成员的整数倍。
基本数据类型所占字节数
类型 字节
char 1
short int 2
int 2(16bit)/4(32bit)/4(64bit)
long 4(16bit)/4(32bit)/8(64bit)
指针变量 4
float 4
double 8
long long 8
long double 10
各种数据类型所占字节长度，主要是int型,long型和指针数据类型的差异。
- int型数据，如果是16bit平台,则是2个字节，如果是32bit的，则占4个字节,64bit仍然是4字节。
- long型数据，如果是16bit平台,则是4个字节，如果是32bit的，则占4个字节,64bit仍然是8字节。
- 指针型数据，比较特殊，大多是4个字节，只有在16bit平台，并且指针式段内寻址时才是2个字节。
另外注意：sizeof(表达式)这样的使用，sizeof是给出其操作数所需要占用的内存大小，在编译时就可以确定。因此不需要去计算表达式的值； 因此有：
int i = 3;
cout << sizeof(i++) << endl;
cout << i << endl;
输出4,3。i++根本没有执行。
虚函数和纯虚函数的区别
定义一个函数为虚函数，不代表函数为不被实现的函数，定义它为虚函数是为了允许用基类的指针来调用子类的这个函数。定义一个函数为纯虚函数，才代表函数没有被实现，定义他是为了实现一个接口，起到一个规范的作用，规范继承这个类的程序员必须实现这个函数。 虚函数有实现，纯虚函数没有方法的实现。包含纯虚函数的类将成为抽象类，不可实例化对象。纯虚函数必循在其子类中进行重写，不然其子类也成为抽象类。不能实例化对象。
虚基类成员的可见性
假定通过多个派生路径继承名为X的成员，有下面三种可能性：
- 如果在每个路径中 X 表示同一虚基类成员，则没有二义性，因为共享该成员的单个实例。
- 如果在某个路径中 X 是虚基类的成员，而在另一路径中 X 是后代派生类的成员，也没有二义性——特定派生类实例的优先级高于共享虚基类实例。
- 如果沿每个继承路径 X 表示后代派生类的不同成员，则该成员的直接访问是二义性的。 像非虚多重继承层次一样，这种二义性最好用在派生类中提供覆盖实例的类来解决。 特殊的初始化语义：通常，每个类只初始化自己的直接基类。如果使用常规规则，就可能会多次初始化虚基类。类将沿着包含该虚基类的每个继承路径初始化。为了解决这个重复初始化问题，从具有虚基类的类继承的类对初始化进行特殊处理。在虚派生中，由最低层派生类的构造函数初始化虚基类。虽然由最低层派生类初始化虚基类，但是任何直接或间接继承虚基类的类一般也必须为该基类提供自己的初始化式。只要可以创建虚基类派生类类型的独立对象，该类就必须初始化自己的虚基类，这些初始化式只有创建中间类型的对象时使用。
不能使用宏开始或者结束注释
#define BSC //
#define BMC /*
#define EMC */
- （1）BSC my single-linecomment
- （2）BMC my multi-linecomment EMC
（1）和（2）都错误，因为注释先于预处理指令被处理，当这两行被展开成
//…或/*…*/时,注释已处理完毕此时再出现//…或/*…*/自然错误。
C++中模板的编译过程
- 第一遍扫描到模板定义时将token流存入语法树中，不做其它操作
- 第二遍当模板被实例化时用模板实参代入进行运算，将所有的模板参数换为实参进行语法和语义分析 特别需要注意的是类模板的成员函数只有在调用的时候才会被实例化。
C++局部变量，全局变量，静态变量的作用域，生命期
C++变量根据定义位置的不同，具有不同的作用域，作用域可分为6种：全局作用域，局部作用域，语句作用域，类作用域，命名作用域和文件作用域。
从作用域看
- 全局变量：具有全局作用域。全局变量只需在一个源文件中定义，就可以作用于所有的源文件。当然，其他不包括全局变量定义的源文件需要用extern关键字再次声明这个全局变量。
- 静态局部变量：具有局部作用域。它只被初始化一次，自从第一次初始化直到程序结束都一直存在，他和全局变量的区别在于全局变量对所有的函数都是可见的，而静态局部变量只对定义自己的函数体始终可见。
- 局部变量：也只有局部作用域，他是自动对象，他在程序运行期间不是一直存在，而是只在函数执行期间存在，函数的一次调用结束后，变量就被撤销，其所占用的内存也被收回。
- 静态全局变量：也具有全局作用域，他与全局变量的区别在于如果程序包含多个文件的话，他作用于定义它的文件里，不能作用到其他文件里，即被static关键字修饰过的变量具有文件作用域。这样即使两个不同的源文件都定义了相同的静态全局变量，他们也是不同的变量。
从分配内存空间看
全局变量、静态局部变量、静态全局变量都在静态存储区分配空间，而局部变量在栈分配空间。全局变量本身就是静态存储方式，静态全局变量当然也是静态存储方式。这两者在存储方式上没有什么不同。区别在于非静态全局变量的作用域是整个源程序，当一个源程序由多个源文件组成时，非静态的全局变量在各个源文件中都是有效的。而静态全局变量则限制了其作用域，即只在定义该变量的源文件内有效，在同一源程序的其他源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内，只能为该源文件内的函数公用，因此可以避免在其他源文件中引起错误。
- 静态变量会被放在程序的静态数据存储区里，这样可以在下一次调用的时候还可以保持原来的赋值。这一点是他与堆栈变量和堆变量的区别
- 变量用static告知编译器，自己仅仅在变量的作用域范围内可见。这一点是他与全局变量的区别。
从以上分析可以看出，把局部变量改变为静态变量后是改变了他的存储方式，即改变了他的生存期。把全局变量改变为静态变量后是改变了他的作用域，限制了他的使用范围，因此static这个说明符在不同的地方起的作用是不同的。
TIPS
- 若全局变量仅在单个文件中访问，则可以讲这个变量修改为静态全局变量。
- 若全局变量仅在单个函数中使用，则可以将这个变量修改为该函数的静态局部变量。
- 全局变量、静态局部变量、静态全局变量都存放在静态数据存储区。
- 函数中必须要使用static变量的情况：当某函数的返回值为指针类型时，则必须是static的局部变量的地址作为返回值，若为auto类型，则返回为错指针。
char的整型运算
char a = '5';
char b = '6';
cout << a+b << endl; // 输出107
a = a - '0';
cout << a << endl; // 输出 ♣
附：ASCII码
0:48、A:65、a:97
'A' == 'a'-32
define中为何经常会使用 do{…}while(0);来包装多条语句代码
do{…}while(0)的目的是为了在for循环和if语句时，避免出现下面的情况：
#define xxx i++; i--;
for (I = 0 ; I < 10; I ++) xxx;
展开后变为
for ( I = 0 ; I < 10; I ++ ) I ++; I --;
(对define中do{}while(0)的理解)
define的一些注意点
#define SQR(x) printf("Thesquareof x is%d.\n",((x)*(x)));
如果这样使用宏：
SQR(8);
则输出为：
The squareof x is 64.
注意，引号中的字符x被当作普通文本来处理，而不被当作一个可以被替换的语言符号。假如确实希望在字符串中包含宏参数，那就可以使用#，它可以把语言符号转化为字符串。上面的例子改一改：
#define SQR(x) printf("The squareof "#x" is%d.\n",((x)*(x)));
再使用：
SQR(8);
则输出的是：
The squareof 8 is 64.
- 求两个数的平方
#define SQR(x) x * x假设x的值是个表达式
10+1，SQR(x)被替换后变成10+1*10+1这并不是想要得到的。括起来就好了：#define SQR(x) （（x）*（x））求两个数的和：
#define SUM (x)（x）+（x）而代码又写成这样：
SUM (x)* SUM (x)替换后变成：
（5*3）+（5*3）*（5*3）+（5*3）所以又错了！所以最外层的括号最好也别省了。 要搞定宏定义表达式其实很简单，别吝啬括号就行了。 注意这一点：宏函数被调用时是以实参代换形参。而不是值传送。
- 和#运算符一样，##运算符可以用于宏函数的替换部分。这个运算符把两个语言符号组合成单个语言符号。看例子：
#define XNAME(n) x##n如果这样使用宏：
XNAME(8)则会被展开成这样：x8##就是个粘合剂，将前后两部分粘合起来。
static、const、volatile、typeof关键字的用途描述
- static：静态函数、静态变量、静态类成员
- const：const变量，const指针、const函数
- volatile：多线程共享变量
- typeof：获取类型值
std::vector实现原理及特定场景下的改进
- 说一下std::vector的实现原理，主要讲一下和内存管理相关的内容
- 常驻内存程序，一个std::vector的生命周期和程序生命周期相同，且会频繁的调用std::vector的push_back()和clear()方法，调用clear()方法时，vector.size()小于1万的概率为0.95,vector.size()可能出现的最大值为100万。如果程序中有多个这样的std::vector实例，程序长期运行后，会导致内存持续增长，一定时间后，可能将内存耗尽。请问，如何用较小的代价修改vector的设计，来避免内存持续增长问题。 答：
- 内存不够用时，双倍扩容。clear()时，不释放内存，以减少内存分配次数。
- 修改clear()方法，当vector.size() 大于1万时，释放内存。
STL中的stable_sort()的时间复杂度是多少
stable_sort()使用的算法类似于自适应算法，当空间足够的时，时间复杂度是O(nlogn)；当空间比较紧张时，时间复杂度是O(nlogn*logn)。
机器代码对有条件执行指令的支持方式
C语言中的某些结构，比如条件语句、循环语句、分支语句，要求有条件地执行。机器代码提供两种基本的低级机制来实现有条件的行为。除了整数寄存器，CPU还维护着一组单个位的条件码寄存器用于描述最近的算术或逻辑操作的结果。可以检测这些寄存器来执行条件分支指令。常用的条件码有： CF:进位标志，最近的操作使最高位产生了进位，可以用来检查无符号操作数的溢出； ZF:零标志，最近的操作得出的结果为0； SF:符号标志，最近的操作得到的结果为负数； OF:溢出标志，最近的操作导致一个补码溢出（正溢出或负溢出）
跳转指令会导致执行切换到程序中一个全新的位置，在汇编代码中，跳转的目的地通常用一个label表示。 如：
int absdiff(int x, int y){
if(x < y){
return y - x;
}
else{
return x - y;
}
}
以上C语言代码将被编译为如下汇编代码：x在%ebp+8中，y在%ebp+12中
movl 8(%ebp),%edx 获取x
movl 12(%ebp),%eax 获取y
cmpl %eax,%edx 比较x和y
jge .L2 如果>=，则跳转.L2
subl %edx,%eax 计算y-x
jmp .L3 无条件跳转.L3
.L2:
subl %eax,%edx 计算x-y
movl %edx,%eax 两种情况下返回值都放在%eax中
.L3: 结束
C语言中提供了多种循环结构，do-while、while、for等。可以使用条件测试和跳转组合起来实现循环的效果。大多数汇编器会根据一个循环的do-while形式来产生循环代码，其他的循环会首先转换成do-while形式，再编译成机器代码。
条件传送指令
实现条件操作的传统方法是利用控制的条件转移，当条件满足时程序沿着一条执行路径进行，而当条件不满足时，就走另一条路径。这种机制比较简单，但在现代处理器上可能会非常低效。条件转移是一种替代策略：先计算一个条件操作的两种结果，然后再根据条件是否满足从而选取一个，只有在一些受限的情况下这种策略才可行，但是如果可行，就可以用一条简单的条件传送指令来实现它。条件传送指令更好地匹配了现代处理器的性能特性。
使用条件表达式实现absdiff函数：
int absdiff(int x,int y){
return x < y ? y-x :x-y;
}
生成的汇编代码如下：
movl 8(%ebp),%ecx 获取x
movl 12(%ebp),%edx 获取y
movl %edx,%ebx 复制y
subl %ecx,%ebx 计算y-x
movl %ecx,%eax 复制x
subl %edx,%eax 计算x-y，并设置为返回值
cmpl %edx,%ecx 比较x，y
cmovl %ebx,%eax 如果<，则将返回值替换为y-x !!! 仅需一条指令图（条件传送指令）
以上汇编代码类似于如下的C语言代码：
int tval = y-x;
int rval = x-y;
int test = x<y;
// 只需一条指令
if(test) {
rval = tval;
}
return rval;
基于条件数据传送的代码比基于条件控制转移的代码性能好，原因在于：现代处理器使用流水线方式来执行指令，这种方式通过重叠连续指令的步骤来获得高性能，例如正在取一条指令的时候执行它前面一条指令的算术运算。要做到这一点，要求能够事先确定要执行指令的序列，这样才能够保持流水线中充满了待执行的指令。当机器遇到条件跳转时，它常常还不能确定是否会进行跳转，处理器使用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行，如果它的猜测比较可靠，指令流水线中就会充满着指令，但是如果猜测错误，则处理器要丢掉它为该跳转指令后所有指令已经做了的工作，然后再开始从正确位置处起始的指令去填充流水线。这样一个错误的预测会导致大约20~40个时钟周期的浪费。 与条件跳转不同，处理器可以执行条件传送而无需预测测试的结果，处理器只是读源值，检查条件码，然后要么更新目的寄存器，要么保持不变。 使用条件传送也不是总会改进代码的效率，如果条件求值需要大量的计算，那么当相应的条件不满足时，这些工作就白费了。对gcc的实验表明，只有当两个表达式都很容易计算时（即所谓的受限情况）它才会使用条件传送。
过程（函数）调用的机器级实现
一个过程调用包括将数据（参数、返回值）和控制从代码的一部分传递到另一部分，在进入过程时为过程的局部变量分配空间，在退出时释放这些空间。大多数机器只提供转移控制到过程和从过程中转移出控制等简单的指令，数据传递、局部变量的分配和释放通过程序栈来操作。
机器用栈来传递参数、存储返回信息、保存寄存器用于以后恢复以及本地存储等。为单个过程分配的那部分栈称为栈帧（stack frame）。栈帧以两个指针界定，寄存器%ebp为帧指针，寄存器%esp为栈指针，当程序执行时，栈指针可以移动，因此大多数信息的访问都是相对于帧指针（即帧指针为当前栈帧的固定起点）的。
[栈底]
+================+
- -
- ... - [较早的帧]
- -
+================+
- ... -
- 参数n - [调用者的帧]
- 参数1 -
- 返回地址 -
+================+
- %ebp -
- ... -
- 临时变量 - [当前帧]
- -
+================+ <-- %esp
[栈顶]
假设过程P调用过程Q，则Q的参数放在P的栈帧中，P中的返回地址被压入栈中，形成P的栈帧的末尾。返回地址就是当程序从Q返回时应该继续执行的地方。过程Q也用栈来保存其他不能存放在寄存器中的局部变量，以及Q调用的其他过程的参数。
栈向低地址方向增长，而栈指针%esp指向栈顶元素，可以用pushl将数据存入栈中并利用popl指令从栈中取出。将栈指针的值减小一定的值可以分配没有指定初始值的数据空间，也可以通过增加栈指针来释放空间。
CPU支持以下过程调用和返回的指令：
call Label 过程调用
call *Operand 过程调用
leave 为返回准备栈
ret 从过程调用中返回
call指令的效果是将返回地址入栈，并跳转到被调用的过程的起始处。返回地址是在程序中紧跟在call后面的那条指令的地址，当被调用的过程返回时，执行会从此处继续。ret指令从栈中弹出地址，并跳转到这个位置。
Y86指令集体系结构
- 每条指令都会读取或修改处理器状态的某些部分。
- Y86有8个寄存器
%eax、%ecx、%edx、%ebx、%esi、%edi、%esp、%ebp。每个寄存器存储一个字，%esp被入栈、出栈、调用和返回指令作为栈指针，在其他情况下寄存器没有固定的含义或固定值。 - 有3个1位的条件码：ZF（零）、SF（符号）、OF（溢出），它们保存最近的算术或逻辑指令所造成影响的有关信息。
- 程序计数器PC存放当前正在执行指令的地址。
- 存储器从概念上讲是一个很大的字节数组，保存程序和数据，Y86程序用虚拟地址来引用存储器位置，硬件和操作系统一起将虚拟地址翻译成实际物理地址。
- 状态码Stat表明程序执行的总体状态，如正常运行还是出现了某种异常。
Y86指令集只包括四字节整数操作，寻址方式和操作也比较少，以下是Y86支持的所有指令的表述：
汇编码 字节编码
halt 0 0
nop 1 0
rrmovl rA,rB 2 0 rA rB r->r 从寄存器移往寄存器
irmovl V,rB 3 0 F rB V i->r 从立即数移往寄存器
rmmovl rA,D(rB) 4 0 rA rB D r->m 从寄存器移往存储器
mrmovl D(rB),rA 5 0 rA rB D m->r 从存储器移往寄存器
注：不允许直接从存储器地址传送到另一个存储器地址，也不允许将立即数传送到存储器。
OPl rA,rB 6 fn rA rB D
OP代表4种整数操作指令：addl、subl、andl、xorl，这些指令会设置3个条件码ZF、SF、OF
jXX Dest 7 fn Dest
jXX代表7个跳转指令：jmp、jle、jl、je、jne、jge、jg。
cmovXX rA,rB 2 fn rA rB
cmovXX代表6个传送指令：cmovle、cmovl、cmove、cmovne、cmovge、cmovg;只有当条件码满足所需要的约束时，才会更新目的寄存器的值。
call Dest 8 0 Dest
将返回地址入栈，然后跳到目的地址，ret指令用于从这样的过程中返回。
ret 9 0
pushl rA A 0 rA F 入栈
popl rA B 0 rA F 出栈
其指令编码长度从1个字节到6个字节不等。一条指令含有一个单字节的指令指示符，可能含有一个单字节的寄存器指示符，还可能含有一个4字节的常数字。字段fn指明是某个整数操作OPl、数据移动条件cmovXX或者分支条件jXX。
程序寄存器存在CPU中的一个寄存器文件中，这个寄存器文件就是一个小的、以寄存器ID作为地址的随机访问存储器。
指令集的字节编码必须具有唯一的解释，任意一个字节序列要么是一个唯一的指令序列的编码，要么就不是一个合法的字节序列。（具体指令编码，略）
循环展开
循环展开通过增加每次迭代计算的元素的数量，减少循环的迭代次数。 对于整数加法和乘法，循环展开使CPE有所改进，但是对于浮点数运算却没有，即循环展开不能改进浮点数运算（与CPU进行浮点数计算的方式有关）。
void combine5(vec_ptr v,data_t *dest){
long int i;
long int length = vec_length(v);
long int limit = length - 1;
data_t *data = get_vec_start(v);
data_t acc =IDENT;
// 循环展开2次
for(i = 0; i < limit; i+=2){
acc = (acc OP data[i]) OP data[i+1];
}
for(; i<length; i++){
acc = acc OP data[i];
}
*dest = acc;
}
+ * + F* D*
combine4 2.00 3.00 3.00 4.00 5.00
combine5 2.00 1.50 3.00 4.00 5.00
编译器可以很容易地执行循环展开，如gcc可以使用-funroll-loops选项来执行循环展开。
处理器预测错误处罚
当分支预测逻辑不能正确预测一个分支是否需要跳转的时候，条件分支可能会导致严重的预测错误处罚。处理器的工作超前于正在执行的指令，如果指令遵循的是一种简单的顺序，那么这种指令流水线化就能很好地工作，当遇到分支的时候，处理器必须猜测分支该往哪个方向走。对于条件转移的情况，这意味着要预测是否会选择分支，对于间接跳转或过程返回这样的指令，这意味着预测目标地址。
如果预测是正确的，那么处理器就会提交投机执行的指令的结果，把它们存储到寄存器或存储器中，如果预测结果是错误的，处理器必须丢弃掉所有投机执行的结果，在正确的位置重新开始取指令的过程。对于i7来说，预测错误处罚是44个时钟周期。
最新的x86处理器有条件传送指令，在编译条件语句和表达式时，gcc能够产生使用这些指令的代码，而不是更传统的基于控制的条件转移的实现。翻译成条件传送的基本思想是计算出一个条件表达式或语句两个方向上的值，然后用条件传送选择期望的值。条件传送指令可以被实现为普通指令流水线化处理的一部分，没有必要猜测条件是否满足，因此猜测错误也没有处罚。
现代处理器中的分支预测逻辑非常善于辨别不同的分支指令有规律的模式和长期的趋势，因此不要过分关心可预测的分支。对于无法预测的情况，如果编译器能够产生使用条件数据传送而不是使用条件控制转移的代码，可以极大地提高程序的性能，这不是C语言程序可以直接控制的，但是有些表达条件行为的方法能够更直接地被翻译成条件传送，而不是其他操作。 如下两个函数实现同样的功能：将a[i]设置为a[i]和b[i]中较小的那一个，将b[i]设置为较大的那一个。
void minmax1(int a[], int b[], int n){
int i;
for(i=0; i<n; i++){
if(a[i] > b[i]){
int t = a[i];
a[i] = b[i];
b[i] = t;
}
}
}
void minmax2(int a[], int b[], int n){
int i;
for(i=0; i<n; i++){
if(a[i] > b[i]){
int min = a[i] < b[i] ? a[i] : b[i];
int max = a[i] < b[i] ? b[i] : a[i];
a[i] = min;
b[i] = max;
}
}
}
使用随机数据测试minmax1，CPE大约为14.50，使用可预测的数据，CPE大约为3.00~4.00。 对于minmax2，无论哪种类型的数据，CPE大约都为5.0
编写高速缓存友好的代码
局部性比较好的程序更容易有较低的不命中率，因而往往运行的更快。应该试着去编写高速缓存友好的代码。包括以下方法： 1.让最常见的情况运行得快：程序通常把大部分时间花在少量核心的函数上，而这些函数通常把大部分时间花在少量的循环上，因此应该把注意力集中在核心函数的循环上，而忽略其他部分。 2.在每个循环内部缓存不命中数量最小：对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文件中。步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块。
高速缓存对程序性能的影响
存储器系统的性能不是一个数字就能描述的，它是一座时间和空间局部性的存储器山（一个变化很大的程序局部性的函数）。
考虑一对nn的矩阵相乘问题，矩阵乘法通常由三个嵌套循环实现，分别用索引i、j、k表示，改变循环次序可以得到矩阵乘法的6个在功能上等价的版本。从高层来看，这6个版本的功能是一样的，总共都执行O(n^3)个操作，且加法和乘法的数量相同。但是分析最里层循环迭代的行为可以发现在访问数量和局部性上是有区别的。 假设： C = AB，AB为nn的数组。只有一个高速缓存，其块大小为32字节，数组n很大，以至于矩阵的一行都不能完全装进L1高速缓存中。
// ijk版本
for(i=0; i<n; i++){
for(j=0; j<n; j++){
sum = 0.0;
for(k=0; k<n; k++){
sum += A[i][k] * B[k][j];
}
C[i][j] += sum;
}
}
// jki版本
for(j=0; j<n; j++){
for(k=0; k<n; k++){
r = B[k][j];
for(i=0; i<n; i++){
C[i][j] += A[i][k]*r;
}
}
}
// kij版本
for(k=0; k<n; k++){
for(i=0; i<n; i++){
r = A[i][k];
for(j=0; j<n; j++){
C[i][j] += B[k][j]*r;
}
}
}
其他版本略，性能测试结果如下：
ijk&jik jki&kji kij&ikj
每次迭代加载次数： 2 2 2
每次迭代存储次数： 0 1 1
每次迭代A不命中次数： 0.25 1.00 0.00
每次迭代B不命中次数： 1.00 0.00 0.25
每次迭代C不命中次数： 0.00 1.00 0.25
每次迭代总不命中次数： 1.25 2.00 0.50
对于大的n值，即使每个版本都执行相同数量的浮点数算术操作，最快的版本（不命中次数最小）比最慢的版本运行得几乎快20倍。
目标文件的形式
目标文件有3种形式： 1.可重定位目标文件：可以在编译时与其他可重定位目标文件合并以创建一个可执行目标文件。 2.可执行目标文件：可以被直接拷贝到存储器并执行。 3.共享目标文件：一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载到存储器并链接。 可重定位目标文件（包括共享目标文件）由编译器和汇编器生成，可执行目标文件由链接器生成。
如果i=5；那么 a=(++i)–;之后，a和i的值各是多少
a=6, I = 5;
多态类中的虚函数表是Compile-Time，还是Run-Time时建立的?
编译时建立。 对C++ 了解的人都应该知道虚函数（Virtual Function）是通过一张虚函数表（Virtual Table）来实现的。简称为V-Table。 在这个表中，主是要一个类的虚函数的地址表，这张表解决了继承、覆盖的问题，保证其容真实反应实际的函数。这样，在有虚函数的类的实例中这个表被分配在了 这个实例的内存中，所以，当我们用父类的指针来操作一个子类的时候，这张虚函数表就显得由为重要了，它就像一个地图一样，指明了实际所应该调用的函数。 这里我们着重看一下这张虚函数表。在C++的标准规格说明书中说到，编译器必需要保证虚函数表的指针存在于对象实例中最前面的位置（这是为了保证正 确取到虚函数的偏移量）。 这意味着我们通过对象实例的地址得到这张虚函数表，然后就可以遍历其中函数指针，并调用相应的函数。
strcpy,memcpy,sprintf的区别及前两个函数的实现
strcpy 函数操作的对象是 字符串，完成 从 源字符串 到 目的字符串 的 拷贝 功能。
snprintf 函数操作的对象 不限于字符串：虽然目的对象是字符串，但是源对象可以是字符串、也可以是任意基本类型的数据。这个函数主要用来实现 （字符串或基本数据类型）向 字符串 的转换 功能。如果源对象是字符串，并且指定 %s 格式符，也可实现字符串拷贝功能。
memcpy 函数顾名思义就是 内存拷贝，实现 将一个 内存块 的内容复制到另一个 内存块 这一功能。内存块由其首地址以及长度确定。程序中出现的实体对象，不论是什么类型，其最终表现就是在内存中占据一席之地（一个内存区间或块）。因此，memcpy 的操作对象不局限于某一类数据类型，或者说可 适用于任意数据类型，只要能给出对象的起始地址和内存长度信息、并且对象具有可操作性即可。鉴于 memcpy 函数等长拷贝的特点以及数据类型代表的物理意义，memcpy 函数通常限于同种类型数据或对象之间的拷贝，其中当然也包括字符串拷贝以及基本数据类型的拷贝。
char*strcpy(char*strDest, const char*strSrc)
{
assert((strDest != NULL) && (strSrc != NULL));
char *address = strDest;
while ((*strDest++ = *strSrc++) != '')
continue;
return address;
}
void *memcpy(void *pvTo, const void *pvFrom, size_t size)
{
assert((pvTo != NULL) && (pvFrom != NULL)); // 使用断言
byte *pbTo = (byte *) pvTo; // 防止改变pvTo 的地址
byte *pbFrom = (byte *) pvFrom; // 防止改变pvFrom 的地址
while(size -- > 0 )
*pbTo ++ = *pbFrom ++ ;
return pvTo;
}
从N个数中挑选出最小的m个数。N很大，比如100万个，但是可以一次加载到内存
a) m很小时，维护一个m长度的链表，遍历一遍，替换即可 b) 堆排序 c) 败者树 d) 类快速排序 e) 类似于count sort的方法，适用于unique数的个数较少且分布较集中的情况。 f) 如果是字符串，可以hash或者trie树
任意挑选一种JVM，描述垃圾回收的实现机制。
λ 最常规的实现方式是计数器法，但是会存在循环引用的问题 λ 循环引用的问题可以使用对象树遍历的方法 λ 垃圾回收时内存的使用需要考虑内存碎片的问题，可以采用有用对用整体迁移的方法，但是同时需要考虑时间效率开销。
如何实现一个getElementsByClassName(dom, className)方法，以获得所有包含某一个className的所有dom结点
解决问题需要两步： 1． 如何获取所有dom结点的集合，方法是document.getElementsByTagName(‘*’); 2． 遍历每一个结点时，如何判断是否包含某一个className，方法是对className属性使用空格进行split，再遍历是否包含特定className
如何实现一个JSON对象的拷贝
1． 使用递归，对JSON进行树遍历，判断每一个叶子结点的类型，并拷贝 2.实现JSON的序列化，然后反向Eval获取拷贝对象
请说明JAVA不需要程序员回收内存的保障机制。请列举2~~3个JAVA的垃圾回收机制算法，说明基本思想和主要优缺点。
- 引用计数： 当每一次创建一个对象并赋给一个变量时，引用计数器置为1。当对象被赋给任意变量时，引用计数器每次加1当对象出了作用域后(该对象丢弃不再使用)，引用计数器减1，一旦引用计数器为0，对象就满足了垃圾收集的条件。优点是基于引用计数器的垃圾收集器运行较快，不会长时间中断程序执行；缺点是增加了程序分配对象的开销，而且会存在循环引用问题，要借助环检测算法保证形成环的待回收内存能被处理。
- 标记&清除： 以根集开始扫描，对可达对象进行标记，标记完后清除掉未标记（不再存活）的对象。思想是为了解决引用计数的分配开销的缺点而来，但本身存在内存碎片的问题。
- 压缩算法： 为解决标记清除算法的碎片问题，将堆一侧的存活对象，在清理过程中拷贝到堆的另一侧。缺点是通常实现中会增加句柄和句柄表，有额外开销。
- 拷贝算法： 将堆分成对象面和空闲面，对象面满的时候进行回收，将存活的对象拷贝到空闲面，切换对象面和空闲面。优点是解决了压缩算法的句柄等开销，缺点则是堆空间的空闲面始终占据内存，并且拷贝过程耗时较多。常见的是stop-and-copy算法，在切换对象和空闲面的时候停止程序运行。
- 按代回收算法（generation）： 上面提到的拷贝算法要拷贝所有存活对象，而根据“多数对象存在的时间比较短，少数的存在时间比较长”的思路，generation算法把堆分成多个，从最年轻的子堆开始收集，子代存活的对象升级到老一代的子堆中。从而减少了拷贝所有存活对象的代价。
- 另外还有一些算法：火车（train，类似于按代回收）算法、增量收集、并行（多线程）收集、并发（GC与应用程序同时运行，尽量减少打断应用程序的时间）收集、自适应（根据堆情况选择不同的算法）等，不再多赘述。
