Apr
16
今天看到80386+里 BSF/BSR 这对指令貌似挺有意思，Bit Scan Forward/Reverse，它们的作用是正向/逆向扫描一个WORD(16bit)/DWORD(32bit)，找出第一个等于1的bit编号。比如对于BX=0x1010，执行 BSF CX, BX 得到的CX=4，而 BSR CX, BX 得到的CX=12。
咋一看是个神器啊。《编程之美》什么的，不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位，秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期，不过这里的数据指出，在80486+，BSF需要6～43个时钟周期才能完成（BSR则需要6～104个clocks），也就是说，它似乎并没有被特别优化，而是使用了CPU内的微码来完成循环，所以不要指望能带来性能上的BONUS，详情可参见这篇：求整数中比特为1的二进制位数。
这篇文章里面给出的用上BSF/BSR的代码是：
想试试这段代码，不过蛋疼的是这是VS的汇编语法，GCC不能识别，于是终于下了决心翻出GCC-Inline-Assembly-HOWTO，看了下，其实也不是很复杂，简单改了下，变成这样：
跑了一下，果然效率不行，跟最差的直接循环在同一个量级。
仔细看了下代码，发现这里用的是BSR，而且还用上了n和count两个变量，感觉不太爽，于是完全改成汇编，写成这样：
结果。。。基本没变。嗯，所以就这样吧。。。
咋一看是个神器啊。《编程之美》什么的，不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位，秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期，不过这里的数据指出，在80486+，BSF需要6～43个时钟周期才能完成（BSR则需要6～104个clocks），也就是说，它似乎并没有被特别优化，而是使用了CPU内的微码来完成循环，所以不要指望能带来性能上的BONUS，详情可参见这篇：求整数中比特为1的二进制位数。
这篇文章里面给出的用上BSF/BSR的代码是：
int f4(unsigned int num) {
int count = 0;
while(num) {
int n;
__asm {
bsr eax, num
mov n, eax
}
++count;
num ^= (1 << n);
}
return count;
}
int count = 0;
while(num) {
int n;
__asm {
bsr eax, num
mov n, eax
}
++count;
num ^= (1 << n);
}
return count;
}
想试试这段代码，不过蛋疼的是这是VS的汇编语法，GCC不能识别，于是终于下了决心翻出GCC-Inline-Assembly-HOWTO，看了下，其实也不是很复杂，简单改了下，变成这样：
int f4(unsigned int num) {
int count = 0;
while(num) {
int n;
__asm__ (
"bsr %1, %%eax\n\t"
"movl %%eax, %0\n\t"
: "=r" (n)
: "r" (num)
: "%eax"
);
++count;
num ^= (1 << n);
}
return count;
}
int count = 0;
while(num) {
int n;
__asm__ (
"bsr %1, %%eax\n\t"
"movl %%eax, %0\n\t"
: "=r" (n)
: "r" (num)
: "%eax"
);
++count;
num ^= (1 << n);
}
return count;
}
跑了一下，果然效率不行，跟最差的直接循环在同一个量级。
仔细看了下代码，发现这里用的是BSR，而且还用上了n和count两个变量，感觉不太爽，于是完全改成汇编，写成这样：
int f4(unsigned int num) { //注：x86下一般都是用EAX来存函数的返回值
asm (
"movl $0, %%eax\n\t" //这里是eax存的就是count
"jmp f4_cmp\n"
"f4_loop:\n\t"
"bsf %0, %%ecx\n\t" //ecx=bsf(num)
"incb %%cl\n\t" //cl += 1
"shrl %%cl, %0\n\t" //num >>= cl; shr貌似只接受 cl 和立即数？
"incl %%eax\n" //count++
"f4_cmp:\n\t"
"cmp $0, %0\n\t"
"jnz f4_loop\n\t"
:
: "r"(num)
: "%eax", "%ecx"
);
}
asm (
"movl $0, %%eax\n\t" //这里是eax存的就是count
"jmp f4_cmp\n"
"f4_loop:\n\t"
"bsf %0, %%ecx\n\t" //ecx=bsf(num)
"incb %%cl\n\t" //cl += 1
"shrl %%cl, %0\n\t" //num >>= cl; shr貌似只接受 cl 和立即数？
"incl %%eax\n" //count++
"f4_cmp:\n\t"
"cmp $0, %0\n\t"
"jnz f4_loop\n\t"
:
: "r"(num)
: "%eax", "%ecx"
);
}
结果。。。基本没变。嗯，所以就这样吧。。。
Mar
18
在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重复平方算法来实现，提高效率。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
同样O(log(n))的递归算法其实很容易理解：
但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制（比如n=13， 1101），然后一位一位地推。
试推了一下从高位到低位，倒是挺简单的，记B[i]为第 i 位的值，通过A[i] = A[i+1]^2 * x^B[i] 从高到低计算出A[0]，就得到结果了。但是问题是，为了从高到低计算，又得一次递归，似乎不能满足要求。
于是只好反过来，从低位往高位推。这个过程其实也挺简单的，举例来说：
当n=13，即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时，最终结果
ans = x^n % m
= x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
= [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m
也就是说，从低到高，在第 i 位的时候，将 x^(Bit[i] * 2^i) % m 乘到结果中即可。这里可以稍微变换一下：仅当Bit[i] == 1的时候，将x^(2^i) % m乘进去即可。所以这里可以用一个辅助的变量 b 来保存 x^(2^i) % m，在每次迭代的过程中 b = b^2 % m 。
于是实现就容易了：
//网上搜了下模重复平方算法，居然没有靠谱的算法解释，看来可能还是这个算法太简单了吧。。。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
同样O(log(n))的递归算法其实很容易理解：
/* C */
int square(int x) { return x * x; } /* 这里可不能用宏哟 */
int fast_mod(int x, int n, int m)
{
if (n == 0)
return 1;
else if (n % 2 == 0)
return square(fast_mod(x, n / 2, m)) % m;
else
return x * fast_mod(x, n - 1, m) % m;
}
#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
(define (square x) (* x x))
(cond ((= n 0) 1)
((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
(else (remainder (* x (mod-fast x (- n 1) m)) m))))
(mod-fast 79 24 33)
;16
int square(int x) { return x * x; } /* 这里可不能用宏哟 */
int fast_mod(int x, int n, int m)
{
if (n == 0)
return 1;
else if (n % 2 == 0)
return square(fast_mod(x, n / 2, m)) % m;
else
return x * fast_mod(x, n - 1, m) % m;
}
#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
(define (square x) (* x x))
(cond ((= n 0) 1)
((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
(else (remainder (* x (mod-fast x (- n 1) m)) m))))
(mod-fast 79 24 33)
;16
但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制（比如n=13， 1101），然后一位一位地推。
试推了一下从高位到低位，倒是挺简单的，记B[i]为第 i 位的值，通过A[i] = A[i+1]^2 * x^B[i] 从高到低计算出A[0]，就得到结果了。但是问题是，为了从高到低计算，又得一次递归，似乎不能满足要求。
于是只好反过来，从低位往高位推。这个过程其实也挺简单的，举例来说：
当n=13，即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时，最终结果
ans = x^n % m
= x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
= [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m
也就是说，从低到高，在第 i 位的时候，将 x^(Bit[i] * 2^i) % m 乘到结果中即可。这里可以稍微变换一下：仅当Bit[i] == 1的时候，将x^(2^i) % m乘进去即可。所以这里可以用一个辅助的变量 b 来保存 x^(2^i) % m，在每次迭代的过程中 b = b^2 % m 。
于是实现就容易了：
/* C */
int fast_mod_iter(int x, int n, int m)
{
int a = 1, b = x; //i=0的时候b = x^(2^0) = x
while (n)
{
if (n % 2 == 1)
a = a * b % m;
b = b * b % m;
n /= 2;
}
return a;
}
#Python
def fast_mod(x, n, m):
a = 1
b = x
while True:
if n == 0:
return a
if n % 2 == 1:
a = a * b % m
b = b * b % m
n /= 2
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
(define (iter a b n)
(cond ((= n 0) a)
((even? n)
(iter a (remainder (* b b) m) (/ n 2)))
(else
(iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
(iter 1 x n))
(mod-fast-iter 79 24 33)
;16
int fast_mod_iter(int x, int n, int m)
{
int a = 1, b = x; //i=0的时候b = x^(2^0) = x
while (n)
{
if (n % 2 == 1)
a = a * b % m;
b = b * b % m;
n /= 2;
}
return a;
}
#Python
def fast_mod(x, n, m):
a = 1
b = x
while True:
if n == 0:
return a
if n % 2 == 1:
a = a * b % m
b = b * b % m
n /= 2
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
(define (iter a b n)
(cond ((= n 0) a)
((even? n)
(iter a (remainder (* b b) m) (/ n 2)))
(else
(iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
(iter 1 x n))
(mod-fast-iter 79 24 33)
;16
//网上搜了下模重复平方算法，居然没有靠谱的算法解释，看来可能还是这个算法太简单了吧。。。
Mar
18
最近在看SICP，抛弃旧的世界观和方法论压力很大，不过还是很有收获的，比如学习了个O(log(n))的fibonacci算法，大涨姿势啊。
想起前几天看到的某个笔试题，说是用最快的办法计算fibonacci数列的第n项。虽然我知道它是有个通项公式的，但是不适用于精确计算，因此写了个迭代的算法，自以为已经很好了，现在看了真是too simple sometimes naive了。
众所皆知 fibonacci 的定义是f(n) = f(n - 1) + f(n - 2); f(1) = f(2) = 1（从f(1)=1开始算起）
不幸的是这样树形展开效率太低了，当n=42的时候，C语言需要的时间已经超过1s了。
因此需要改成迭代版，使用 (a, b) <- (a + b, a) 这样的方式。
虽然O(n)的效率已经有显著的提升，但是由于这个数列的增长超过了2^n，所以当对于稍大的n，就需要使用大整数的运算，效率很低。python版的代码，当n=300,000的时候，需要超过1s才能得出结果；Scheme版则需要大约9s。
SICP的练习1-19里面则提到一个O(log(n))的巧妙算法：将计算fibonacci的每次迭代 (a, b) <- (a + b, a) 表示为一个变换T[p=0, q=1]，具体表示为（似乎是用矩阵乘法倒推过来的）
通过计算 T[pq](T[pq](a, b)) （即对(a, b)进行两次T[pq]变换），可以得到
也就是说——可以通过类似分治计算 《a的n次方模b》 的算法来计算fibonacci了！
给出了算法以后，代码就容易写了：
经过这样的优化以后，效率显著，对于n=300,000，python版仅需要不到0.04s，而Scheme版也仅需要0.12s即可得出结果。
p.s. 以上代码均经过测试。
想起前几天看到的某个笔试题，说是用最快的办法计算fibonacci数列的第n项。虽然我知道它是有个通项公式的，但是不适用于精确计算，因此写了个迭代的算法，自以为已经很好了，现在看了真是too simple sometimes naive了。
众所皆知 fibonacci 的定义是f(n) = f(n - 1) + f(n - 2); f(1) = f(2) = 1（从f(1)=1开始算起）
#Python版：
fibonacci = lambda n: 1 if n <= 2 else fibonacci(n - 1) + fibonacci(n - 2)
/* C版 */
int fibonacci(int n) {
return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
;Scheme版
(define (fibonacci n) (if (<= n 2) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
fibonacci = lambda n: 1 if n <= 2 else fibonacci(n - 1) + fibonacci(n - 2)
/* C版 */
int fibonacci(int n) {
return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
;Scheme版
(define (fibonacci n) (if (<= n 2) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
不幸的是这样树形展开效率太低了，当n=42的时候，C语言需要的时间已经超过1s了。
因此需要改成迭代版，使用 (a, b) <- (a + b, a) 这样的方式。
#Python版
def fibonacci(n):
a = 1; b = 0;
for i in range(n):
a, b = a + b, a
return b
/* C版 */
int fibonacci(int n) {
int a = 1, b = 0, c;
while (n--) {
c = a;
a = a + b;
b = c;
}
return b;
}
;Scheme版
(define (fibonacci n)
(define (iter n a b)
(if (= n 0) b (iter (- n 1) (+ a b) a)))
(iter n 1 0))
def fibonacci(n):
a = 1; b = 0;
for i in range(n):
a, b = a + b, a
return b
/* C版 */
int fibonacci(int n) {
int a = 1, b = 0, c;
while (n--) {
c = a;
a = a + b;
b = c;
}
return b;
}
;Scheme版
(define (fibonacci n)
(define (iter n a b)
(if (= n 0) b (iter (- n 1) (+ a b) a)))
(iter n 1 0))
虽然O(n)的效率已经有显著的提升，但是由于这个数列的增长超过了2^n，所以当对于稍大的n，就需要使用大整数的运算，效率很低。python版的代码，当n=300,000的时候，需要超过1s才能得出结果；Scheme版则需要大约9s。
SICP的练习1-19里面则提到一个O(log(n))的巧妙算法：将计算fibonacci的每次迭代 (a, b) <- (a + b, a) 表示为一个变换T[p=0, q=1]，具体表示为（似乎是用矩阵乘法倒推过来的）
引用
T[pq](a, b) = (a(p+q) + bq, aq + bp)
通过计算 T[pq](T[pq](a, b)) （即对(a, b)进行两次T[pq]变换），可以得到
引用
(a((pp+qq) + (2pq+qq)) + b(2pq+qq), a(2pq+qq) + b(pp+qq))
记 p' = pp + qq, q' = 2pq+qq 则有
T[p'q'](a, b) = T[pq](T[pq](a, b)) = (a(p' + q') + bq', aq' + bp')
于是
f(n+1) = T[pq]n(f(1))
记 p' = pp + qq, q' = 2pq+qq 则有
T[p'q'](a, b) = T[pq](T[pq](a, b)) = (a(p' + q') + bq', aq' + bp')
于是
f(n+1) = T[pq]n(f(1))
也就是说——可以通过类似分治计算 《a的n次方模b》 的算法来计算fibonacci了！
给出了算法以后，代码就容易写了：
#Python版
def fibonacci(n):
def iter(a, b, p, q, n):
if n == 0:
return b
elif n % 2 == 0:
return iter(a, b, p * p + q * q, 2 * p * q + q * q, n / 2)
else:
return iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1)
return iter(1, 0, 0, 1, n)
/* C版 */
typedef unsigned long long ull;
ull fibo_iter(ull a, ull b, ull p, ull q, int n) {
if (n == 0)
return b;
else if (n % 2 == 0)
return fibo_iter(a, b, p *p + q * q, 2 * p * q + q * q, n / 2);
else
return fibo_iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1);
}
ull fibonacci(int n) {
return fibo_iter(1, 0, 0, 1, n);
}
/* Scheme版 */
(define (even? n) (= (remainder n 2) 0))
(define (fibonacci n)
(define (iter a b p q n)
(cond ((= n 0) b)
((even? n)
(iter
a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ n 2)))
(else
(iter
(+ (* a (+ p q)) (* b q))
(+ (* a q) (* b p))
p
q
(- n 1)))))
(iter 1 0 0 1 n))
def fibonacci(n):
def iter(a, b, p, q, n):
if n == 0:
return b
elif n % 2 == 0:
return iter(a, b, p * p + q * q, 2 * p * q + q * q, n / 2)
else:
return iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1)
return iter(1, 0, 0, 1, n)
/* C版 */
typedef unsigned long long ull;
ull fibo_iter(ull a, ull b, ull p, ull q, int n) {
if (n == 0)
return b;
else if (n % 2 == 0)
return fibo_iter(a, b, p *p + q * q, 2 * p * q + q * q, n / 2);
else
return fibo_iter(a * (p + q) + b * q, a * q + b * p, p, q, n - 1);
}
ull fibonacci(int n) {
return fibo_iter(1, 0, 0, 1, n);
}
/* Scheme版 */
(define (even? n) (= (remainder n 2) 0))
(define (fibonacci n)
(define (iter a b p q n)
(cond ((= n 0) b)
((even? n)
(iter
a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ n 2)))
(else
(iter
(+ (* a (+ p q)) (* b q))
(+ (* a q) (* b p))
p
q
(- n 1)))))
(iter 1 0 0 1 n))
经过这样的优化以后，效率显著，对于n=300,000，python版仅需要不到0.04s，而Scheme版也仅需要0.12s即可得出结果。
p.s. 以上代码均经过测试。
Nov
27
昨天关注了下 微信公众平台，的确是个好东西，赞一下tx近来的开放。
它的api 乍一看还是挺简单的，于是就写了个小东西玩玩。
但是在开发的过程中遇到了多个坑，通过有故事王国的@ctqmumu同学把问题转了过去。实际开发的过程中遇到了好几个问题，但是其他问题（包括发一条消息请求我两次）都莫名其妙消失了，只有一个问题（具体见后文）通过被喷的方式解决了。
总之最后是可以用了，于是多花了点时间，把代码完善了下，写好了注释和样例，放在了Google Code上面，有需要的同学可以拿去用。
下载地址：http://code.google.com/p/mmsdk/downloads/list
注：目前callback url仅支持80端口(@2012.11.27)
#UPDATE 2012.11.29 添加了对图片消息的支持（样例）、对调试的支持（DUMP请求/回复的xml文件），测试SAE可用（调试功能除外）
== 分割线，下面是纯吐槽 ==
它的api 乍一看还是挺简单的，于是就写了个小东西玩玩。
但是在开发的过程中遇到了多个坑，通过有故事王国的@ctqmumu同学把问题转了过去。实际开发的过程中遇到了好几个问题，但是其他问题（包括发一条消息请求我两次）都莫名其妙消失了，只有一个问题（具体见后文）通过被喷的方式解决了。
总之最后是可以用了，于是多花了点时间，把代码完善了下，写好了注释和样例，放在了Google Code上面，有需要的同学可以拿去用。
下载地址：http://code.google.com/p/mmsdk/downloads/list
注：目前callback url仅支持80端口(@2012.11.27)
#UPDATE 2012.11.29 添加了对图片消息的支持（样例）、对调试的支持（DUMP请求/回复的xml文件），测试SAE可用（调试功能除外）
== 分割线，下面是纯吐槽 ==
Nov
25
C/C++标准里头都没有正则表达式，C++还好，可以用上boost::regex，C的话，最简单的还是用系统自带的正则库了。
这个正则库真是相当简单，如果不关心内部琐碎的细节，实际上它只有2个类型、4个函数和7个常量，详细的后面会列出来（或者直接man regex），这里还是直接看例子比较实在：
代码1：email格式检测
这个正则库真是相当简单，如果不关心内部琐碎的细节，实际上它只有2个类型、4个函数和7个常量，详细的后面会列出来（或者直接man regex），这里还是直接看例子比较实在：
代码1：email格式检测
#include <stdio.h>
#include <regex.h>
#include <assert.h>
int main() {
//分配一个regex_t
regex_t reg;
//编译（使用POSIX扩展模式、并忽略大小写），确认编译成功（返回0）
assert(regcomp(®, "^[a-z0-9_]+@([a-z0-9-]+\\.)+[a-z0-9]+$", REG_EXTENDED | REG_ICASE) == 0);
int ret = regexec(®, "steve@rim.jobs", 0, NULL, 0); //执行搜索
//看看返回值：0表示匹配成功，1表示REG_NOMATCH
printf("ret = %d, nomatch = %d\n", ret, REG_NOMATCH);
regfree(®); //记得释放空间
}
#include <regex.h>
#include <assert.h>
int main() {
//分配一个regex_t
regex_t reg;
//编译（使用POSIX扩展模式、并忽略大小写），确认编译成功（返回0）
assert(regcomp(®, "^[a-z0-9_]+@([a-z0-9-]+\\.)+[a-z0-9]+$", REG_EXTENDED | REG_ICASE) == 0);
int ret = regexec(®, "steve@rim.jobs", 0, NULL, 0); //执行搜索
//看看返回值：0表示匹配成功，1表示REG_NOMATCH
printf("ret = %d, nomatch = %d\n", ret, REG_NOMATCH);
regfree(®); //记得释放空间
}
Oct
30
比赛的起因是这样的，@Tranch同学在SegmentFault.com提了个问题，求一个代码，可以列出字符串"qwerty"被 "." 分割的所有情况，比如 q.werty qwe.rty q.w.e.r.t.y 等等。
这个问题其实很简单，qwerty中间最多可以塞5个". "，每个地方用1表示塞，0表示不塞，也就是正好循环 2^5 次就行了（对于全0的情况不做特别要求，可有可无），实现起来也非常容易，这里是写这篇文章时补充的一个C语言实现：
不过当时没想写这样的代码，而是特意脑抽用python写了个递归的版本:
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器，于是一时兴起，简化成了这个等价但是更难读的版本：
虽然已经很短了，但是我还是想知道，是否有更简单些的实现（一定程度上可以忽略效率和可读性），于是在MSTC的群里发了这个问题，简单起见，把字符串改成了"abcde"，问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来，被喷“能不能用人话”。这段代码看起来是有些费解，主要思路是，生成 ['****', '***.', '**..', '*...', '....'] 的各种排列，然后用zip('abcd', p)交错组合起来（再删掉'*'）：
然后 @霄妹纸 说，实际上那个是笛卡尔积。于是用上itertools.product，再改善下语法，可以写成这样，看起来就清晰多了：
@霄妹纸 还给出了另外两个奇葩的代码，一个是 C 的，充分利用和宏、main函数的参数和递归：
另一个是ruby的:
由于不懂ruby语法，所以这个代码我也只能勉强看看，不过思路上跟上面的python代码是一样的，使用笛卡尔积生成组合序列，然后再与'abcde'交错组合。
结果是，ruby赢了（58个字节），python紧随其后（80字节，不包括import），C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义，不过可以对比下，不同的语言（C/Ruby/Python）、不同的编程范型（过程式/函数式）的表达方式，一窥函数式编程的魅力～
这个问题其实很简单，qwerty中间最多可以塞5个". "，每个地方用1表示塞，0表示不塞，也就是正好循环 2^5 次就行了（对于全0的情况不做特别要求，可有可无），实现起来也非常容易，这里是写这篇文章时补充的一个C语言实现：
#include <stdio.h>
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
不过当时没想写这样的代码，而是特意脑抽用python写了个递归的版本:
def add_dots_l(str):
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器，于是一时兴起，简化成了这个等价但是更难读的版本：
def add_dots(s):
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
虽然已经很短了，但是我还是想知道，是否有更简单些的实现（一定程度上可以忽略效率和可读性），于是在MSTC的群里发了这个问题，简单起见，把字符串改成了"abcde"，问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来，被喷“能不能用人话”。这段代码看起来是有些费解，主要思路是，生成 ['****', '***.', '**..', '*...', '....'] 的各种排列，然后用zip('abcd', p)交错组合起来（再删掉'*'）：
from itertools import permutations as p #itertools.permutations是python2.6引入的
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
然后 @霄妹纸 说，实际上那个是笛卡尔积。于是用上itertools.product，再改善下语法，可以写成这样，看起来就清晰多了：
from itertools import product #itertools.product也是2.6引入的
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
@霄妹纸 还给出了另外两个奇葩的代码，一个是 C 的，充分利用和宏、main函数的参数和递归：
#define z(a,b) printf(#a"%s",(x>>b)&1?".":""),
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
另一个是ruby的:
p ("b".."e").inject(["a"]){|a,q|a.product [q,"."+q]}.map &:join
如果是ruby 1.9+的话，还可以再少几个字符：p (?b..?e).inject([?a]){|a,q|a.product [q,?.+q]}.map&:join
由于不懂ruby语法，所以这个代码我也只能勉强看看，不过思路上跟上面的python代码是一样的，使用笛卡尔积生成组合序列，然后再与'abcde'交错组合。
结果是，ruby赢了（58个字节），python紧随其后（80字节，不包括import），C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义，不过可以对比下，不同的语言（C/Ruby/Python）、不同的编程范型（过程式/函数式）的表达方式，一窥函数式编程的魅力～
Jun
30
这是2012年百度实习招聘非技术类的某道笔试题。
给一个5×5的矩阵，每个元素只能是0或者1。
请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？
==== 分割线 ====
乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。
然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。
最简单的做法就是
一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。
更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。
再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。
到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
(p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）
于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。
==== 分割线 ====
扩展：
1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？
根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。
2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)
这个结论就不那么直接了，对M*N有一定的限制。
给一个5×5的矩阵，每个元素只能是0或者1。
请问，有多少种不同的矩阵，能够满足每一行、每一列都有偶数个1？
==== 分割线 ====
乍看这个题目，觉得是数学题。画了个5*5的矩阵，试图填几个数字进去看看是否可以推出一些结论。果断失败。
然后想了下，这题如果枚举的话，也就是2的25次方，大约3200万这个规模，不是很夸张。于是决定暴力搞一下。
最简单的做法就是
for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++;
这个check_even(i)里头把 i 当成一个25bit的二进制数字，并转换为对应的5*5矩阵，判断其每一行和每一列是否满足要求。（p.s. whusnoopy的做法是直接使用位运算，更简单，不过思路就断了。。）一个不难想到的优化是，在for之前先把每一行给枚举了，这样就不需要在check_even里面每次进行转换，只需要从 i 中取出对应的bits，就可以直接找到每一行。
更进一步，由于题目要求每一行都是偶数个1，所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了，枚举出5行，然后判断每个列。很容易计算，每行5个bit，偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。
再进一步剪枝——题目要求所以列是偶数，那么在已经确定前4行的情况下，第5行是可以直接推出来的，需要枚举的矩阵数量降至16^4。但还需要做的事情是，判断第5行是否有偶数个1。
到了这一步，豁然开朗——因为很容易证明，第5行必然是偶数个1：
1) 每一列都是偶数个1（ABCDE都是偶数），所以矩阵中必然有偶数个1（F=A+B+C+D+E为偶数）
2) 前4行都是偶数个1（HIJK都是偶数），所以第5行必然是偶数个1（L=F-H-I-J-K为偶数）
(p.s. 这个证明是WHUMSTC群里某同学给出的，非常清晰，所以我就不给我自己那个很挫的证明过程了）
于是开头的直觉获胜，问题的答案就是：16^4，也就是(2^4)^4。
==== 分割线 ====
扩展：
1. 如果矩阵的大小是 N×N ，甚至是 M×N 呢？
根据上述结论，很容易推知，对于M*N的矩阵，结果是2^((M-1) * (N-1))。
2. 如果要求满足每一行、每一列都有奇数个1呢？(whusnoopy提出)
这个结论就不那么直接了，对M*N有一定的限制。
May
20
从哪儿说起呢？我想了想，从 gets 说起可能最好。
初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……
或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。
这就是典型的溢出攻击。
为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。
这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。
加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。
strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
比较诡异的两件事情是：
1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符
2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充
以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。
事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。
众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。
参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
初学C语言的时候，如果要输入一行字符串，该怎么办？看书，或者找老师，或者找学长，通常得到的答案是gets。用法很简单，似乎也很好用，但是很不幸，这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符，而面对的输入是1万个字符，那么几乎毫无疑问，这个程序是要崩溃的，除非运气特别好，或者……
或者给出的输入是经过精心设计的，例如一段shell code，及其对应的跳转地址。对于常见的计算机体系来说，函数调用时，返回地址是在栈上的，通过精心设计输入，使得溢出数据中的跳转地址好正好覆盖了该返回地址，于是函数在返回时不是如预期般回到调用者处，而是跳转到攻击者给出的shell code处，使得攻击者获得了额外的权限。
这就是典型的溢出攻击。
为了防止这种情况的出现，在C库函数中，许多对字符串操作的函数都有其"n兄弟"版本，例如strncmp，strncat，snprintf……兄弟版本的基本行为不变，但是通常在参数中需要多给出一个整数n，用于限制操作的最大字符数量（本句不够严谨，详情参见各函数的说明）。
这是技术上的解决方案。只是，代码都是人写出来的，总会有对溢出缺乏概念的人，写出令人蛋疼的代码。于是一些公司，例如（听说）腾讯，建立了一套规则，对提交的代码进行扫描，若发现使用了非“n兄弟”版本，就会给对应的码农一定的惩罚措施，从而在管理上降低此类问题出现的可能性。
加强管理当然是好事，但是也给某些有强迫症的码农带来了不便：因为strlen没有n兄弟版本，坑爹啊！事实上，更坑爹的是strcpy，在c语言标准里，它不但没有n兄弟版本，甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。
strncpy 到底做了什么事情呢？它基本上等同于这样几行代码：
char* strncpy(char *dest, const char *src, size_t n){
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[i] = src[i];
for ( ; i < n ; i++)
dest[i] = '\0';
return dest;
}
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[i] = src[i];
for ( ; i < n ; i++)
dest[i] = '\0';
return dest;
}
比较诡异的两件事情是：
1. 如果src的前n个字符里面没有'\0'，那么它不会在末尾补上这个结束符
2. 如果拷贝的数据不满n个字符，那么它会用 '\0' 在末尾填充
以 strcpy 的行为来理解它，只会感到很蛋疼：第一点很可能会造成此后代码的数组越界访问，而第二点则是对cpu资源的浪费。
事实上，完全是因为历史的原因，造成了这样的误会。在第七版的UNIX文件系统中，每个inode结构体中包含的每个entry（对应文件或下级目录）只有16个字节，其中前两个用于标识inode，剩下的14个用于保存文件名。由于文件名最长只能有14个字符，所以在设计上，末尾不足的字符用'\0'来填充；如果达到14个字符，则不需要结束标志。
众所皆知，c是为unix而生，所以这就是strncpy的原始目的：定长字符串 的拷贝。对应的代码，很自然地，可以这样写：
strncpy(inode->d_name, filename, 14);
那么如果确实需要一个strcpy的n兄弟版本该怎么办呢？最简单的办法是用snprintf：
snprintf(dest, n, "%s", src);//注意，不能直接用src来替换"%s"
p.s. 其实还有个 strlcpy ，只可惜它是OpenBSD 2.4引入的，并非C标准中的函数，适用范围较窄。
参考资料：
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
