本文介紹的常數優化方法能使代碼加速到原來的一半甚至更快

使用union類

定義

union是一種特殊的類，定義方法如下（定義在main內或main外都可以）

union Union{
	int a;
	double b;
	char c;
};
Union u;

互斥的特性

union的所有成員存儲在同一個地址上，因此在任意時刻，union中只能有一個成員有值，例如以下代碼就是錯誤的

U.a = 27;
U.b = 6.7;
cout << U.a;
return 0;

正是由於此特性，union不僅節約空間，而且使得變量更容易被存儲到高速緩存中，從而起到常數優化作用

在union中加入對象

可以在union中加入對象，例如

class Class{
	int a;
};
union Union{
	Class test;
	int n;
};

以上代碼如果要通過union修改a的值，需要將a定義為public，如下

#include<bits/stdc++.h>
using namespace std;
class Class{
public:
	int a;
};
union Union{
	Class test;
	int n;
};
Union u;
int main(){
    u.test.a = 114;
    cout << u.test.a;
    return 0;
}

以上代碼可以正常運行，如果將第4行的public改為private或protected，則不能編譯

一個循環分多路執行

以下兩段代碼

int sum = 0;
for(int i = 1; i <= n; i++){
	sum += a[i];
}

和

int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
for(int i = 1; i <= n; i += 4){
	sum1 += a[i];
	sum2 += a[i + 1];
	sum3 += a[i + 2];
	sum4 += a[i + 3];
}

前者運行時間大約是後者的兩倍

位運算小技巧

這部分引自《論程序底層優化的一些方法和技巧》

無分支地求絕對值

int abs(int x){
	int y = (x >> 31);
	return (x + y) ^ y;
}

無分支地求最大值

int max(int x, int y){
	int m = (x - y) >> 31;
	return y & m | x & (~m);
}

不使用除法求平均數

int average(int x, int y){
	return (x & y) + ((x ^ y) >> 1);
}

不使用中間變量交換兩個數（節約空間）

void swap(int &x, int &y){
	x ^= y;
	y ^= x;
	x ^= y;
}

使原來為a的x變為b

x ^= a ^ b;

高維數組尋址非常慢

舉個例子，與其寫

if(a[i][j][k][l] > a[i][j][k - 1][l] + a[i][j][k][l - 1]){
	a[i][j][k][l] += a[i][j][k - 1][l] + a[i][j][k][l - 1];
}

不如寫成

int &p = a[i][j][k][l], tmp = a[i][j][k - 1][l] + a[i][j][k][l - 1];
if(p > tmp){
	p += tmp;
}

這樣優化的效果在dp中尤其明顯

另外，某一維很小，如

dp[10000000][2]

則應當定義為大小為10000000的結構體或兩個數組，如下

struct DP{
	int a, b;
}dp[10000000];
//or
dp0[10000000], dp1[10000000];

而在這兩種寫法中，又推薦使用結構體

高維數組儘量按內存連續訪問

不能避免使用高維數組時，應注意這一點

以下兩段代碼

int a[10000][10000], sum = 0;
for(int i = 0; i < 10000; i++){
	for(int j = 0; j < 10000; j++){
		sum += a[i][j];
	}
}

和

int a[10000][10000], sum = 0;
for(int i = 0; i < 10000; i++){
	for(int j = 0; j < 10000; j++){
		sum += a[j][i];
	}
}

後者運行時間大約是前者的3倍，如果數組的大小是2的整數次冪，後者運行時間會達到前者的10倍以上

避免將多維數組某一位的大小定義為2的冪

根據《論程序底層優化的一些方法和技巧》中的測試，遍歷一個2048 * 2048的數組比遍歷一個2049 * 2049的數組慢大約4倍，所以，請不要將多維數組某一維的大小定義為2的冪，儘量將多維數組的每一維大小都定義為奇數。

ps.尤其是開狀壓dp數組，記得大小+1