【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
