ACM竞赛卡常技巧[AIGC] 250519

幂次运算替换

x*2^k => x<<k;

x/2^k => x<<k;

x *= 2; → x << 1;     // 加速300%  
x /= 64; → x >> 6;    // 加速350%

取模运算优化

x = x % 4; → x & 3;   // 加速600%（仅限模数为2^n）

奇偶判断优化

if (x % 2 == 0) → if ((x & 1) == 0)  // 加速600%

绝对值加速

i = x < 0 ? -x : x; → i = (x ^ (x >> 31)) - (x >> 31);  // 加速600%

变量交换

// 传统交换 → XOR交换（加速20%）  
a ^= b; b ^= a; a ^= b;

前缀自增优化
```
for (i=0; i<n; i++) → for (i=0; i<n; ++i)  // 加速5-10%  
```
- 原理：避免临时对象生成（对迭代器显著）

循环展开

// 4次展开 → 加速50-100%  
for (i=0; i<n; i+=4) { s0+=a[i]; s1+=a[i+1]; ... }

倒序循环

for (i=n-1; i>=0; --i) → 比正序快10%（某些CPU架构）

STL容器预分配
```
vector<int> a;        → vector<int> a(100);  
for (i=0;i<100;i++)   → for (i=0;i<100;i++)  
    a.push_back(x);       cin >> a[i];           // 加速100%  
```
- 原理：避免动态扩容时的内存重分配（push_back触发2倍扩容策略）
- 更优写法：a.reserve(100)（不初始化元素，但预分配空间）
多维数组维度顺序
```
int dp[2][10][1e5] → int dp[1e5][10][2]  // 加速200-300%  
```
- 原理：提升缓存局部性（大维度在前）

寄存器变量

register int a;  // 加速5-15%（C++11后效果有限）

内联函数

inline int add(int a, int b) { return a+b; }  // 加速20-50%

快速幂算法

// 位运算版 → 比递归版快300%  
while (n) { if (n&1) res*=a; a*=a; n>>=1; }

快读模板

// 自定义read() → 比scanf快3-5倍  
while (ch >= '0') x = (x<<3)+(x<<1)+ch-'0';

批量输出缓冲

setvbuf(stdout, new char[1<<20], _IOFBF, 1<<20);  // 加速10倍

编译指令

#pragma GCC optimize("O3,unroll-loops")     // 整体加速30-50%  
#pragma GCC target("avx2,bmi2")             // SIMD指令加速特定算法

分支预测提示

if (__builtin_expect(condition, 0))  // 加速10-20%（GCC专用）

为什么未提及浮点位移
- 原链接中 x = int(1.232) → 1.232>>0 是错误写法（位移仅限整数）
- 正确优化：int(x) → (int)(x + 0.5)（四舍五入加速15%）
为什么未强调++i与i++差异
- 现代编译器已优化该差异，仅对自定义迭代器类有微小影响