C++ 常用卡常技巧

极限卡时

可以使用头文件<ctime>下的clock()函数，默认是以 $\dfrac {1}{10^6}$ （百万分之一）秒为单位的。

注意：

clock()函数的运行特别慢，如果每次迭代或者搜索都执行一次可能到最后还没执行其他操作，光是这个函数的执行就把时间用完了。

一般可以每迭代或搜索 $10^6$ 次执行一次clock()，若超过时限就强行退出，以达到对时间的极限应用。

CLOCK_PER_SEC这个常数存在于头文件<ctime>中，表示一秒钟内 CPU 运行的时钟周期数，用于将clock()函数的结果转化为以秒为单位的量，但是这个量的具体值是与操作系统相关的。

#include <iostream>
#include <ctime>
using namespace std;
int start = clock();

int main()
{
    for (int i = 0; ; i ++ )
    {
        // 做人不能太贪，超过0.9秒就可以退出了 =,= 其他地方还需要时限
        if (i % 1000000 == 0 && clock() - start >= CLOCKS_PER_SEC * 0.9)
        {
            cout << i << endl;
            cout << clock() - start << endl;
            exit(0);
        }
    }
    return 0;
}

更加接近底层的运算方式（以下转自： 迪克痒，稍微做了点格式优化）

位运算心法：

&（与逻辑）：有 $0$ 出 $0$，全 $1$ 出 $1$；

|（或逻辑）：有 $1$ 出 $1$，全 $0$ 出 $1$；

~（非逻辑）：空即是色，色即是空；

^（异或）：相异出 $1$，相同出 $0$。

其他加速技巧

如果乘上一个 $2$ 的倍数数值，可以改用左移运算， 加速 $300\ \%$

x = x * 2

x = x * 64

改为:

x = x << 1;

x = x << 6;

如果除以一个 $2$ 的倍数数值，可以改用右移运算加速 $350 \%$

x = x / 2;

x = x / 64;

改为:

x = x >> 1;

x = x >> 6;

交换两个变量数值swap(a, b)，使用XOR可以加速 $20 \%$

int t = a;
    a = b;
    b = t;

改为：

a = a ^ b;
b = a ^ b;
a = a ^ b;

正负号转换，可以加速 $300 \%$

i = - i;

改为：

i = ~i + 1; // NOT 写法

或：

i = (i ^ (-1)) + 1; // XOR 写法

取余数，如果除数为 $2$ 的倍数，可利用AND运算加速 $600 \%$

x = 131 % 4;

改为：

x = 131 & (4 - 1);

利用AND运算检查整数是否为 $2$ 的倍数，可以加速 $600 \%$

isEven = (i % 2) == 0;

改为：

isEven = (i & 1) == 0;

绝对值函数abs()的写法，写法1要比内置函数快，且写法2又比写法1加速 $20 \%$

//写法1
i = x < 0 ? -x : x;

//写法2
i = (x ^ (x >> 31)) - (x >> 31);

比较两数值相乘之后是否拥有相同的符号，加速 $35 \%$

eqSign = a * b > 0;

改为：

eqSign = a ^ b > 0;