面试题-C语言

快速求幂

int fast_pow(int a,int b)
{
	int result = 1;
	int base = a;
	while (b != 0)
	{
		if (b % 2) // 指数为奇数
		{
			result *= base;
		}
		base *= base;
		b /= 2;		
	}
	return result;
}

常见位运算

1.将x最右边的n位清零：              x&(~0 << n)
2.获取x的第n位值（0或者1）：        (x>>n)&1
3.获取x的第n位的幂值：              x&(1<<(n-1))
4.仅将第n位置为1：                  x|(1<<n)
5.仅将第n位置为0：                  x&(~(1<<n))
6.将x最高位至第n位(含)清零：         x&((1<<n)-1)
7.将第n位置第0位（含）清零：         x&(~(1<<(n+1)-1))
8.判断奇偶:                         (x&1) == 1  奇数    
				  (x&1) == 0  偶数
9.二分：                            x/2 == x >> 1
10.清零最低位的1：                  x = x&(x-1)
11.得到最低位的1：                  x&(-x)
12.x&(~x) = 0

统计二进制数x中1的个数

int num;
while(x){
    num++;
    x = x & (x - 1);
}

不引入第三变量，交换两个变量的值

//例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现： 
a = a^b； 　　//a=10100111 
b = b^a； 　　//b=10100001 
a = a^b； 　　//a=00000110

快速判断两个值是否相等

1	return ((a ^ b) == 0)

整数的平均值

对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：

 int average(int x, int y)   //返回X,Y 的平均值
{   
    return (x&y)+((x^y)>>1);
}

利用位与（&）提取出两个数相同的部分，利用异或（^）拿出两个数不同的部分的和，相同的部分加上不同部分的和除2即得到两个数的平均值。

计算绝对值

int abs( int x ) 
{ 
int y ; 
y = x >> 31 ; 
return (x^y)-y ; //or: (x+y)^y 
}

原理：
如果x是正数，右移31位之后就变成了0x00000000，x和0x00000000异或，仍然是x,异或之后的x-0x00000000仍然是x;
如果x是负数，右移31位就变成了0xffffffff，x和0xffffffff异或，变成了x连着符号位全部取反，也就是实现了补码取反，补码取反-0xffffffff也就是补码取反再+1，是就上就对应着x的绝对值.
对于右移，因为牵扯到符号位，所以正数右移左边补0，负数右移左边补1。
对于左移，因为不牵扯符号位，所以右边不论正数还是负数都补0。

extern “C” 的作用及理解

extern “C”的作用是告诉C++编译器用C规则编译指定的代码（除函数重载外，extern “C”不影响C++其他特性）。
C和C++的编译规则不一样，主要区别体现在编译期间生成函数符号的规则不一致。C++需要支持重载，单纯的函数名无法区分出具体的函数，所以在编译阶段就需要将形参列表作为附加项增加到函数符号中。

volatile作用和用法

volatile是一个类型修饰符，作用是作为指令关键字，一般都是和const对应，确保本条指令不会因为编译器的优化而忽略。
以下几种情况通常会用到：

并行设备的硬件寄存器（如：状态寄存器）
一个中断服务子程序中会访问到的非自动变量
多线程应用中被几个任务共享的变量

一个参数可以既是const又是volatile吗？

可以。例如只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。

一个指针可以是volatile 吗？

可以，例如当一个中断服务子程序修改一个指向一个buffer的指针。

const常量和#define的区别

编译器处理方式不同

define宏是在预处理阶段展开。
const常量是编译运行阶段使用。

类型和安全检查不同

define宏没有类型，不做任何类型检查，仅仅是展开。
const常量有具体的类型，在编译阶段会执行类型检查。

存储方式不同

define宏仅仅是展开，有多少地方使用，就展开多少次，不会分配内存。宏定义不分配内存，变量定义分配内存。
const常量会在内存中分配(可以是堆中也可以是栈中)。

const可以节省空间，避免不必要的内存分配。

#define PI 3.14159       //常量宏 
const doulbe Pi=3.14159; //此时并未将Pi放入ROM中
double i=Pi;             //此时为Pi分配内存，以后不再分配！
double I=PI;             //编译期间进行宏替换，分配内存 
double j=Pi;             //没有内存分配 
double J=PI;             //再进行宏替换，又一次分配内存！

const提高了效率
编译器通常不为普通const常量分配存储空间，而是将它们保存在符号表中，这使得它成为一个编译期间的常量，没有了存储与读内存的操作，使得它的效率也很高。

使用32位编译情况下，给出判断所使用机器大小端的方法。

大端：低位字节内容放在高地址。
小端：低位字节内容放在低地址。
联合体方法判断方法：利用union结构体的从低地址开始存，且同一时间内只有一个成员占有内存的特性。大端储存符合阅读习惯。联合体占用内存是最大的那个，和结构体不一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>

int main()
{
union w
{
int a;
char b;
}c;
c.a = 1;
if(c.b == 1)
printf("小端存储\n");
else
printf("大端存储\n");
return 0;
}

static的用法

static修饰局部变量：使其变为静态存储方式(静态数据区)，那么这个局部变量在函数执行完成之后不会被释放，而是继续保留在内存中。
static修饰全局变量：使其只在本文件内部有效，而其他文件不可连接或引用该变量。
static修饰函数：对函数的连接方式产生影响，使得函数只在本文件内部有效，对其他文件是不可见的（这一点在大工程中很重要很重要，避免很多麻烦，很常见）。这样的函数又叫作静态函数。使用静态函数的好处是，不用担心与其他文件的同名函数产生干扰，另外也是对函数本身的一种保护机制。

const的用法

const修饰常量：定义时就初始化，以后不能更改。
const修饰形参：func(const int a){};该形参在函数里不能改变。
const修饰类成员函数：该函数对成员变量只能进行只读操作，就是const类成员函数是不能修改成员变量的数值的。被const修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的健壮性。
1
2
3
4
5
const int a;
int const a;
const int *a;
int * const a;
int const * a const;
前两个的作用是一样，a是一个常整型数。
第三个意味着a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。
第四个意思a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。
最后一个意味着a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。

内存对齐

内存对齐作用

平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。

结构体struct内存对齐规则

对于结构体的各个成员，第一个成员的偏移量是0，排列在后面的成员其当前偏移量必须是当前成员类型的整数倍；
结构体内所有数据成员各自内存对齐后，结构体本身还要进行一次内存对齐，保证整个结构体占用内存大小是结构体内最大数据成员的最小整数倍；
如程序中有#pragma pack(n)预编译指令，则所有成员对齐以n字节为准(即偏移量是n的整数倍)，不再考虑当前类型以及最大结构体内类型。

确定结构体占用空间大小

确定实际对齐单位，其由以下三个因素决定

CPU周期：32位默认4字节对齐，64位默认8字节对齐
结构体最大成员(基本数据类型变量)
预编译指令#pragma pack(n)手动设置（n只能填1、2、4、8、16）
上面三者取最小的,就是实际对齐单位

除结构体的第一个成员外，其他所有的成员的地址相对于结构体地址(即它首个成员的地址)的偏移量必须为实际对齐单位或自身大小的整数倍(取两者中小的那个)
结构体的整体大小必须为实际对齐单位的整数倍。
1
2
3
4
5
6
7
typedef struct _nums
{
char a; // 1字节
short b; // 2字节
int c; // 4字节
double d; // 8字节
}nums;
上面nums中，没有手动设置对齐单位，linux64系统的默认对齐单位是8字节，结构体nums的最大成员double d占8个字节，故实际对齐字节是二者最小，即8字节。
char a放在结构体的起始地址;
short b占2个字节，2小于实际对齐字节8，故b的起始地址相对于a的起始地址的偏移量须为2的整数倍个字节;
int c占4个字节，4小于实际对齐字节8，故c 起始地址相对于a的起始地址的偏移量须为4的整数倍个字节；
double d占8个字节，8与实际对齐字节8相等，故d的起始地址相对于a的起始地址的偏移量须为8的整数倍个字节；
所以nums所占空间如下: 1(a)+1(浪费的空间，由b的起始地址决定这1字节必须腾出)+2(b)+4(c)+8(d)=16个字节。

联合体union内存对齐规则

找到占用字节最多的成员；
union的字节数必须是占用字节最多的成员的字节的倍数，而且需要能够容纳其他的成员。
1
2
3
4
5
6
//x64
typedef union {
long i; // 8
int k[5]; // 5*4
char c; // 1
}D
要计算union的大小,首先要找到占用字节最多的成员,本例中是long,占用8个字节,int k[5]中都是int类型,仍然是占用4个字节的，然后union的字节数必须是占用字节最多的成员的字节的倍数,而且需要能够容纳其他的成员,为了要容纳k(20个字节),就必须要保证是8的倍数的同时还要大于20个字节,所以是24个字节。

inline函数

为什么要用inline函数

对于一个代码很少的函数，函数调用时传递参数和得到返回结果的开销可能比函数体内部代码的开销还大，并且编译器生成用于参数传递或返回结果的代码可能比函数体代码占用更多内存，对于这种短小的函数，可以在函数定义前用关键字inline声明为内联函数，从而可避免函数调用的开销，提高程序效率，且使程序代码更短。

注意事项

如果一个声明为内联函数的函数体重包含了循环语句或者函数体代码比较复杂，编译器在编译时，通常并不会对该内联函数的调用进行内联展开。即，编译器不保证一定会对内联函数调用进行内联展开。

关键字inline 必须与函数定义体放在一起才能使函数成为内联，仅将inline 放在函数声明前面不起任何作用。

// 如下风格的函数Foo 不能成为内联函数：
inline void Foo(int x, int y); // inline 仅与函数声明放在一起
void Foo(int x, int y)
{
}

// 而如下风格的函数Foo 则成为内联函数：
void Foo(int x, int y);
inline void Foo(int x, int y) // inline 与函数定义体放在一起
{
}