各种小技巧

    这篇文章的主要目的就是为了自己收集、总结一些编程时的小技巧。示例语言是C++。



/* 判断质数，判断素数
 *
 * 0、1、负数、偶数，都直接false。
 * 剩下只需要判断是否存在奇数因数。最小的非prime奇数是9，所以可以从i=3开始。
 * i*i<p 这个条件是为了减少for循环的次数，即根号优化。
 * */
bool isPrime(int p) {
if (p<2 || !(p%2)) return false;
for (int i=3; i*i<=p; i+=2) {
if (!(p%i)) return false;
}
return true;
}

/* 两个变量交换值，不引入临时变量
 *
 * 注意，应用在较大的动态数组上有时候会出错，不知道原因。发现会出错的话就用临时变量吧。
 * */
void swapWithoutTemp(int& a, int& b) {
a += b;
b = a-b;
a -= b;
}


/* 快速判断一个整数是否为2的正整数次幂
 *
 * 计算机用二进制存储所有内容。
 * 如果n是2的正整数次幂，假设n用x位来表示。
 * 那么n的表示一定是1后面跟(x-1)个0，那么(n-1)的表示一定是0后面跟(x-1)个1。
 * 因此对n和(n-1)进行逻辑与运算，一定会得到0。
 * */
bool isPowerOf2(int n) {
return !(n & (n-1));
}