Skip to content

C++技巧

以下小技巧可以提高比赛中的编程速度，或者提高程序执行效率。

位操作

设置(set)一位: 

     num |= (1 << pos);

清空(clear)一位： 

    num &= (~(1 << pos));

切换(toggle, XOR)一位： 

    num ^= (1 << pos);

检测一位： 

    if (num & (1<<pos)) ...

测试一个整数是否为2的幂： 

int isPowerof2(int x)
{
    return (x && !(x & x-1));       // x & x-1 当x中只有一位为1的时候返回0
}

取最低为1的位（利用补码性质，用在树状数组实现中）： 

    x & -x

逻辑操作

测试0或非0: 

    if (!x) ...                 // 测试0
    if (x)  ...                 // 测试非0

逻辑操作返回0或1: 

    return x == y && !z;        // 当x==y且z非0的时候，返回1，否则返回0

测试x不是-1（这个生僻）： 

    if (~x) ...

数组与struct初始化

全局变量自动初始化为0: 

int x[10000];
int main() {
    ...
}

初始化struct: 

struct Point {int x; int y;};
int main() {
    struct Point p = {1,2};
}

初始化数组为同样的值，std::fill()和std::fill_n()是应该使用的主流方法: 

int main() {
    long long x[1000], y[1000];
    int z[1000], a[1000];
    std::fill_n(x, 1000, 2);        // 最通用的初始化数组办法，也可以：fill(x, x+1000, 2)

    // 其它初始化方法
    int b[1000] = {};               // 初始化为0的简单写法
                                    // 如果写成{1}，那意思是第一个元素是1，后面都是0
    memset(y, -1, sizeof(y));       // 0和-1可以用memset初始化，因为-1LL=0xffffffff_ffffffff
                                    // 注意sizeof(arr)返回数组的总字节数
                                    // 错误：memset(y, 1, sizeof(y))不是设为1，而是一个大数
                                    // -O2下memset比fill快一倍
    memset(z, 0x3f, sizeof(z));     // 0x3f3f3f3f 经常作为正数最大值使用，和0x7f7f7f7f的区别是加上一个整数，依然是正的
    memset(a, 0xc0, sizeof(a));     // 0xc0c0c0c0 最小负数值
}

使用std::pair方便排序

经常碰到需要对包含多个数的结构进行排序的情况，这时如果使用pair，可以省掉comparator的编写，因为pair有默认的comparator，即先按first排序，如果相等，再按second排序。

    vector<pair<int,int>> ps;
    for (int i = 0; i < n; i++) {
        int r,c;
        scanf("%d %d", &r, &c);
        ps.push_back({r,c});
    }
    sort(ps.begin(), ps.end()); // 先按row，再按column排序所有坐标

参考