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排序所有坐标

参考