俄罗斯农民增殖
这是我对俄罗斯农民增殖的简短实施。 怎么改进?
限制 :仅在> 0,b> 0时有效
for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);
它可以通过添加空格,适当的缩进和适当的函数体来改进:
int peasant_mult (int a, int b) { for (p = 0; p += (a & 1) * b, a != 1; a /= 2, b *= 2); return p;}
看到? 现在很清楚如何使用for
声明的三个部分。 请记住,程序主要是为人眼编写的。 不可读的代码总是错误的代码。
现在,为了我的个人娱乐,一个尾递归版本:
(defun peasant-mult(ab&optional(sum 0)) “返回a和b的乘积, 通过农民增殖来实现。“ (如果(= 1) (+ b总和) (农民(地板)(/ 2)) (* b 2) (+ sum(* b(logand a 1)))))))
我认为这很糟糕这与编译器的观点完全相同,并且(希望)更加清晰
int sum = 0; while(1) { sum += (a & 1) * b; if(a == 1) break; a = a / 2; b = b * 2; }
现在我把它写出来了,我明白了。
有一种非常简单的方法可以改善这种情况:
p = a * b;
它甚至具有a或b可以小于0的优点。
如果看看它是如何工作的,你会发现它只是正常的手动乘法执行二进制。 你的计算机以这种方式(1)完成它,因此使用俄罗斯农民方法的最简单方法是使用内置乘法。
(1)也许它有一个更复杂的算法,但原则上你可以说,它适用于这个算法
循环中仍然存在乘法。 如果您想降低乘法的成本,可以使用它:
for(p=0;p+=(-(a&1))&b,a!=1;a>>=1,b<<=1);
我没有发现它特别可怕,混淆或不可读,正如其他人所说的那样,而且我不理解所有这些投票。 这就是说,这就是我如何“改进”它:
// Russian Peasant Multiplication ( p <- a*b, only works when a>0, b>0 ) // See http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication for( p=0; p+=(a&1)*b, a!=1; a>>=1,b<<=1 );
这是代码混淆比赛? 我想你可以做得更好。 对于初学者来说,使用误导性的变量名而不是无意义的变量名。
p
未初始化。
如果a
为零会发生什么?
如果a
是否定的,会发生什么?
更新:我看到您已更新问题以解决上述问题。 虽然您的代码现在似乎按照规定工作(溢出问题除外),但它的可读性仍然低于应有的程度。
我认为它不完整,很难阅读。 你在寻找什么具体的反馈?
int RussianPeasant(int a, int b) { // sum = a * b int sum = 0; while (a != 0) { if ((a & 1) != 0) sum += b; b <<= 1; a >>= 1; } return sum; }
没有乘法或除法的答案:
function RPM(int a, int b){ int rtn; for(rtn=0;rtn+=(a&1)*b,a!=1;a>>=1,b<<=1); return rtn; }