【C++】代码优化的推导与结论
0x00 前言
作者第一次写这类文章，有错误欢迎指出！
有人把代码优化称为骗分，或许被人认为是毫无作用的东西，或许是被认为歪门邪道的方法。然而，就算是骗分所蕴含的知识可不少，同时骗分与打表有着本质上的差别。在比赛中，假设你一道题使用了 \(O(n^2)\) 的时间复杂度来做，或许只能拿 20 分；但是使用了一些优化后，或许能拿 50 分，甚至更高。不过值得一提的是，这些方法通常只用于 OI 赛制，因为 ACM 赛制下，如果得不到满分，拿 99 分也不算做对。
0x10 读写优化
0x11 内存缓冲优化
输入输出，是每个程序必不可少的部分之一。如果把你要读入的内容看成一条路，那么读入就是走这条路。然而，有一些读入的方法没有考虑到内存缓冲，比如 get() 。大家可以理解为 get() 在这条路上走的太快，导致到达终点时没有刹住车，所以其在比赛时禁用。而 scanf通常比 cin 快的原因仅仅只是其内存缓冲处理的比较好。那么如果我们关掉 cin 的内存缓冲，它的效率会高很多吗？答案是肯定的。
cin.tie(0); //这条语句可以关掉 cin 的内存缓冲
cout.tie(0); //与 cin 同理，但作用于 cout
这两句代码放在主函数的第一句话时可以生效，但是这只是基础操作，而且其在比赛时还禁用。所以，我们引来了下一个部分——快读。
0x12 快速读写优化
除了 scanf 和 cin 等常见的读入工具，还有一种读入工具：getchar()。这种读入工具会在生效后读入控制台输入的第一个字符，包括空格，换行符等。因为其只读入一个字符，不用考虑内存缓冲，又因为种种原因，其效率高的惊人。
int a=getchar()
例如以上代码会读入一个字符，但想读入多个却不行（如：我输入了 10 ，但其却只储存了 1 ）。
但如果我们写一个循环，不断地用 getchar() 读入，只要读入的还是数字就继续读入，效率会高吗？答案是会。这种读入方式被称为快读，不仅效率高，而且在比赛中也允许使用。
inline int read()
{
int f=1,res=0; //res 是你输入的值，f 用于判断正负
char c=getchar();
while(c<'0' || c>'9'){ //先把奇怪的东西读入了
if(c=='-') f=-1; //如果是负数，f 变为 -1
c=getchar();
}
while(c>='0' && c<='9'){
res=res*10+c-'0'; //读入部分
c=getchar();
}
return res*f; //返回
}
这就是一个可以读入整数的快读模板，使用 int a=read() 可以快速读入 a 。
练习： 用快读完成 P1001
思考： 想一下能用快读读入字符串吗？如果能，尝试写一个。
0x20 运算优化
0x21 位运算
众所周知，电脑在完成我们交给它的任务时，总是使用二进制在计算。而位运算是直接在二进制时运算，显然，它比四则运算效率会高不少（不妨通过学习一下 C++ 中的进制，以了解进制转换与字符串的关系）。接下来，我将简略介绍一下基础的位运算，如果你已经掌握了基础位运算，可以直接跳过。
-
& 与这是一种双目运算符，当两个参数都为 1 时，答案为 1 ； -
| 或这是一种双目运算符，当任何一个参数为 1 时，答案为 1 ； -
~ 非这是一种单目运算符，答案与参数相反； -
^ 异或这是一种双目运算符，当两个参数不同时，答案为 1 ； -
>> 右移这是一种单目运算符，可以删除最右位； -
<< 左移这是一种单目运算符，作用与右移相反。
注意，以上运算都是在二进制下完成，请看样例：
4 & 7 表示 4 与 7 进行与运算，在二进制下标示为：
100 & 111 ，然后末位对齐，若高位不够需要补 0 。
按以上与操作运算后，得到二进制数：100 ,转换为十进制数就是 4 ，这就是位运算。值得一提的是，位运算不具备短路特性。
综上，你可以使用位运算进行优化你的代码，例如 a<<2 等价于 a*2 。同理, a>>2 等价于 a/2 。或许你会觉得位运算使用范围少，其实在数学部分，状态压缩等程序中，可运用位运算的地方可多了。
练习：用位运算完成下列题目。
例： 将数字 a 的第 k 位设置为 0 用位运算为：a=~(1<<k)&a;
读取数字 a 的第 k 位：
将数字 a 的第 k 位取反：
0x22 位运算对储存的优化
在你了解计算机是如何储存数码之后，或许可以在运算之中找到等价的位运算。不过这类优化运用范围较小，可以只作为了解为主。值得一提的是，计算机储存整数和浮点数是分开来的，而计算机储存出来的浮点数是无限精度的，所以这里只介绍整数的储存。
1.原码
这种记录方法将一串二进制数的首位作为标记，记录其的正负（负数首位为 1 ，正数首位为 0 ）。然而这样运算出来的结果肯定不对，需要特殊判断，所以无法作为正式的方法使用。
2.反码
简单来说，反码就是首位符号位与原码规则相同，但是若数字为负数，其它位全部取反。但因为种种原因，其并不是主要的储存方法。
3.补码
主流的储存方法。其储存方法与反码类似，不同在于，如果储存结果为负数，会给答案加负一。
0x23 位运算对空间的优化
此类优化针对于空间上的优化，基于位运算，不过其优化较小，对于实际应用用处不算特别大。比如交换两个整数变量的值，我们一般会使用:
int t=a;
a=b;
b=t;
显然，这样会浪费 \(O(1)\) 的空间复杂度，如果想节约这点可以忽略不计的空间复杂度，可以使用：
a=a^b;
b=b^a;
a=a^b;
这种技巧用处或许不算大，但是有些技巧却十分有用。比如在二分时，我们求出 mid 通常会使用 mid=(l+r)/2 ，但使用位运算只要 mid(l+r)>>2 即可，通常情况下，它们是等价的，但对于大数据，这种方法可以避免空间超限。总而言之，位运算更多的优化在于时间复杂度上（特别是状压）。
0x30 数据优化
0x31 寄存器优化
有人喜欢在循环时增加寄存器（ regsiter ），或许认为这样会更快，但在实际运行中真的是这样吗？首先，我们要知道寄存器是 CPU 特殊储存器，其无地址，无变量。使用 register 可以直接将变量储存在 CPU 的寄存器中，通常情况下， register 的确可以增加程序的运行速度，但是寄存器在很多运行环境中是禁用的，甚至还会出现 “负优化” 的情况，因此，我并不推荐各位使用寄存器。出于标程，一下放下寄存器的使用实例。
register int a,b;
cin>>a>>b;
for(register int i=1;i<=b;i++) a*=a;
cout<<a;
使用寄存器的方法只需在定义变量时声明即可。
0x32 地址优化
众所周知，系统新建变量时会开辟一个地址，而如果这个变量不再使用，则会释放（具体原理是简单化的 “栈原理” ）。而开辟地址需要时间，回忆学习链表时，曾有使用 new 来新建节点的方法，但效率极低。我们可以通过这种原理来做一些优化。
for(int i=1;i<=100;i++) cout<<"Luogu!"<<endl;
以上的循环定义了一个仅可以在这个 for 循环中使用的临时变量 i ，若需要处理的数据十分多，这样会浪费很多时间复杂度，因此，我们可以改进：
int i;
for(i=1;i<=n;i++) cout<<"Luogu!"<<endl;
这种优化方法确实有用，且不仅是在空间上。进一步，我们可以更多的使用全局变量和宏定义，以此增加程序的效率。例如以下代码：
for(int i=1;i<=999;i++)
for(int j=1;j<=999;j++)
for(int k=1;k<=999;k++)
cout<<"Luogu!"<<endl;
像这种代码想要不超时基本不可能，但如果加上了宏定义就不一定了，如下：
#define fir(i,a,b) for(i=a;i<=b;i++)
......
int i,j,k;
fir(i,1,999)
fir(j,1,999)
fir(k,1,999)
cout<<"Luogu!"<<endl;
虽然这样能提高效率，但想要不超时还是很困难，不过从此可以看出，全局变量和宏定义确实能提高代码效率。
0xFF 结语
如果你已经掌握了这些代码复杂度优化方法，相信你在比赛中至少能多拿个 20 分。
作为学生党，并没有很多的时间来完成博客，甚至还会有很多写错的地方。这类文章（包括这篇）以后会持续更新，所以暂时先完结了。
同步发布于：CSDN
