1 
int x, y; // x is a non-negative integer 
p = 0;
while (x > 0)
{
    if ( x % 2 == 1 )
       p = p + y;
    y = y*2;
    x = x/2;
}
// p == a*b here

我知道这个循环使用代数找到'a'和'b'的乘积：

a * b = (1/2)a * 2b

但我不明白代码：

if ( x % 2 == 1 )
    p = p + y;

我希望有人能解释为什么在 x 的奇数值上将“p”分配为“p + y”。

4

6 回答 6

1

如果 x 是奇数，x = x/2则将 x 设置为比 x/2 小 0.5（因为整数除法会将其向下舍入）。p需要进行调整以允许这样做。

于 2013-09-29T14:43:18.520 回答
1

因为这些都是整数，所以a / 2会是整数。如果a是奇数，则该整数已向下舍入，并且您在b循环的下一次迭代中缺少一半，即循环b的当前迭代中的一个整数（因为b[ y] 每次都加倍）。

于 2013-09-29T14:41:50.497 回答
1

将乘法视为重复加法，x*y 是将 y 加在一起 ​​x 次。这也与将 2*y 相加 x/2 次相同。从概念上讲，如果 x 是奇数，它的含义有些不清楚。比如x=5，y=3，加2.5倍是什么意思？代码注意到 x 何时为奇数，将 y 添加进去，然后 y=y*2 和 x=x/2。当 x 是奇数时，这会丢弃 0.5 部分。所以在这个例子中，你加一次 y，然后 x 变成 2（不是 2.5），因为整数除法会丢弃分数。

在每个循环结束时，对于 p、x 和 y 的当前值，您将看到原始 x 和 y 的乘积等于 p + x*y。循环迭代直到 x 为 0，结果完全在 p 中。

如果您制作一个表格并在每次循环中更新它，它也有助于查看发生了什么。这些是每次迭代开始时的值：

x | y  | p
----------
5 | 3  | 0
2 | 6  | 3
1 | 12 | 3
0 | 24 | 15
于 2013-09-29T14:58:55.383 回答
1 
while (x > 0) {
    if (x % 2 == 1)
        p = p + y;
    y = y*2;
    x = x/2;
}

想象x= 4, y =5

迭代：

  1. x是偶数，y= 10，x= 2（即x可以除，y应该加倍）
  2. x是偶数，y= 20，x= 1
  3. x奇数, p= 20, y= 40, x= 0 (即x不能再除,y应加到p)
  4. x > 0是false，循环结束

p= 4 *y

现在想象x一开始很奇怪，假设x= 5，y= 2：

  1. x奇数, p= 2, y= 4, x= 2
    (5/2 = 2.5,新值x将向下取整，y应在加倍之前加上)
  2. x是偶数，y= 8，x= 1
  3. x是奇数，p= 10，y= 16，x= 0

p= y+ 4*y

首先y是原因，在结果加倍之前将其添加到结果中（1 * y）在这种情况下相当于0.5 * (2 * y)

于 2013-09-29T15:02:38.127 回答
1

这通过观察（例如）来起作用y * 10 = y * 8 + y * 2。

这很像在学校在纸上做乘法。例如，要乘以 14 x 21，我们一次乘一位数（并在需要的地方向左移动），因此我们添加 1x14 + 2 x 14（向左移动一位数）。

    14
  x 21
  ----
    14
   280

在这里，我们正在做几乎相同的事情，但使用二进制而不是十进制。右移与奇数无关，而与简单地查找数字中的哪些位已设置有关。

当我们将一个操作数右移以查找是否设置了某个位时，我们也将另一个操作数左移，就像我们在纸上以十进制进行算术运算时向左移数字加零一样。

因此，以二进制形式查看内容，我们最终会得到如下结果：

      101101
    x  11010
    --------
     1011010
+  101101000
+ 1011010000

如果我们想要，而不是将操作数向右移动，我们可以将掩码向左移动，这样我们就可以使用，然后使用，然后使用，依此类推（事实上，它可能会产生and很多那样更有意义）。然而，无论好坏，在汇编语言中（通常会做这种事情），移动操作数并为掩码使用常量通常比将掩码加载到寄存器中并在需要时移位它要容易一些。1and124

于 2013-09-29T15:06:32.070 回答
0

您应该将 x 重写为 2*b+1 （假设 x 是奇数）。然后

x*y = (2*b+1)*y = (2*b)*y + y = b*(2*y) + y = (x/2)*(2*y) + y

其中 (x/2) 表示整数除法。以这种方式重写操作后，您会看到 x/2、2y 和 +y 出现。

于 2013-09-29T15:21:38.300 回答