判断一个链接有没有环，很著名的算法是Floyd判圈算法，也叫龟兔算法。但是，原来还有一种算法，可以比Floyd更快一点，这种算法叫做Brent判圈算法。 算法思想 用2个指针rabbit和turtle从链表头出发。 rabbit先一步一步走，最多走2步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 这个时候，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走4步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 然后，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走8步，如果走到尽头，则...

最近在看 Hacker's delight ，把一些觉得有用的小技巧记一下来。 /******/ /******/ /******/ /******/ /******/ /******/ 把二进制数x的最右边一位1变成0: x = x & (x - 1) 其中的一个应用是，判断一个正整数是不是2的n次方或者0。 #include <stdio.h> int main() { int i = 0; for (i = 0; i < 1000; ++i) { if ((i & (i - 1)) == 0) { print...

summary : 乘法 对于复数的乘法，我们是这样算的: (a + bi)(c + di) = ac - bd + (bc + ad)i 但是，据说伟大的数学家高斯注意到的一个现象: (bc + ad) = (a + b)(c + d) - ac - bd 这样，原来要进行ac, bd, bc, ad四次乘法，现在就只需要进行(a + b)(c + d), ac, bd 三次乘法，虽然多了几次加法，但是对于计算机来说，乘法计算远比加法慢，在数据量很大的情况 下，这个小技巧将会使算法性能得到极大的提升。...