3

这是我对俄罗斯农民乘法的简短实现。如何改进？

限制：仅在 a>0,b>0 时有效

for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);
4

10 回答 10

55

可以通过添加空格、适当的缩进和适当的函数体来改进它：

int peasant_mult (int a, int b) {
  for (p = 0;
       p += (a & 1) * b, a != 1;
       a /= 2, b *= 2);
  return p;}

看？现在很清楚for声明的三个部分是如何使用的。请记住，程序主要是为人眼编写的。不可读的代码总是坏代码。

现在，为了我个人的乐趣，一个尾递归版本：

(defun 农民-mult (ab &optional (sum 0))
  "返回 a 和 b 的乘积，
   通过农民的繁殖来实现。”
  （如果（= 1）
      (+ b 总和)
      （农民-mult（地板（/ a 2））
                    (* b 2)
                    (+ sum (* b (logand a 1))))))
于 2008-11-04T04:36:03.503 回答
20

我认为这很糟糕从编译器的角度来看，这是完全相同的代码，并且（希望）更清晰

int sum = 0;
while(1)
{
    sum += (a & 1) * b;
    if(a == 1)
       break;

    a = a / 2;
    b = b * 2;
}

现在我已经写出来了，我明白了。

于 2008-11-04T01:28:53.553 回答
14

有一个非常简单的方法可以改善这一点：

p = a * b;

它甚至具有 a 或 b 可以小于 0 的优点。

如果你看看它是如何工作的，你会发现它只是正常的手动乘法执行二进制。您的计算机以这种方式（1）在内部进行操作，因此使用俄罗斯农民方法的最简单方法是使用内置乘法。

(1) 也许它有一个更复杂的算法，但原则上你可以说，它适用于这个算法

于 2008-11-13T10:36:32.540 回答
7

循环中仍然存在乘法。如果你想降低乘法的成本，你可以使用它来代替：

for(p=0;p+=(-(a&1))&b,a!=1;a>>=1,b<<=1);
于 2008-11-04T01:38:12.803 回答
5

正如其他人所说，我并不觉得它特别糟糕、模糊或不可读，而且我不理解所有这些反对意见。这就是说，这就是我将如何“改进”它：

// 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 );
于 2008-11-04T10:12:35.773 回答
4

p未初始化。

如果a为零会怎样？

如果a是负数会怎样？

更新：我看到您已更新问题以解决上述问题。虽然您的代码现在似乎可以正常工作（溢出问题除外），但它的可读性仍然低于应有的水平。

于 2008-11-04T01:27:34.383 回答
4

这是为了代码混淆比赛？我认为你可以做得更好。首先，使用误导性的变量名而不是无意义的变量名。

于 2008-11-04T01:38:48.027 回答
3

我认为它不完整，而且很难阅读。你在寻找什么样的具体反馈？

于 2008-11-04T01:18:49.097 回答
2 
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;
}
于 2008-11-04T02:44:24.667 回答
0

没有乘法或除法的答案：

function RPM(int a, int b){
    int rtn;
    for(rtn=0;rtn+=(a&1)*b,a!=1;a>>=1,b<<=1);
    return rtn;
}
于 2009-07-23T15:30:54.160 回答