0x00 C++代码优化

在这里讲述一些代码优化的奇技淫巧:

0x00 位运算

位运算往往比普通的加减乘除运算快很多,例如:

a2b\frac{a}{2^b}可以写为a >> ba2ba\cdot2^b可以写为a << b

amod2ba\,mod\,2^b 可以写为a & 2^b -1,例如10与4取余即为10 & 3

计算int类型a与b的平均值,如果使用表达式a+b2\frac{a+b}{2}可能会出现a+b溢出的情况,但a+b的平均值只能小于等于max(a, b),也就说绝不会溢出,此处可以使用位运算做一个不会溢出的平均值计算:

1
(a&b)+((a^b)>>1)

不使用临时变量互换两个整数:

1
2
3
x ^= y;
y ^= x;
x ^= y;

0x01 减少运算强度

当计算aba^b时,如果b比较小的话可以直接写成a*a*a的形式避免使用pow函数

使用自增自减运算符来代替诸如i = i + 1这样的运算,i = i + 1往往生成如下汇编代码:

1
2
3
move A,i ; 把x从存储器取出存入累加器A 
add A,1 ; 累加器A加1
store i ; 把新值存回x

如果使用++i的话,对于大多数CPU来说就只有一行汇编指令了:

1
incr i ; i加1

同样,尽量使用++i而不是i++,此处对于迭代器来说同样适用,因为i++往往伴随着多余的存指令和取指令,此处可以对比STL中迭代器重载的前置自增和后置自增运算符代码:

1
2
3
4
5
6
7
8
9
10
11
12
_Vector_iterator& operator++()
{ // preincrement, 前置自增(++i)
++*(_Mybase *)this;
return (*this);
}

_Vector_iterator operator++(int)
{ // postincrement, 后置自增(i++), 需要建立临时变量, 多出来的存取操作
_Vector_iterator _Tmp = *this;
++*this;
return (_Tmp);
}

使用复合表达式,例如将a = a + b改为a += b,这个也是老生常谈了