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

これは、(たとえば) を観察することで機能しy * 10 = y * 8 + y * 2ます。

学校で紙の上で掛け算をするのとほとんど同じです。たとえば、14 x 21 を掛けるには、一度に 1 桁ずつ掛けます (必要に応じて左にシフトします) ので、1x14 + 2 x 14 (1 桁左にシフト) を加算します。

    14
  x 21
  ----
    14
   280

ここでは、ほぼ同じことを行っていますが、10 進数ではなく 2 進数で作業しています。右シフトは、数値が奇数であることとは関係なく、数値のどのビットが設定されているかを単純に見つけることに関係しています。

ビットが設定されているかどうかを調べるために 1 つのオペランドを右にシフトすると、もう 1 つのオペランドも左にシフトします。これは、10 進数で紙の上で算術を行うときにゼロを追加して数値を左にシフトするのと同じです。

したがって、物事をバイナリで表示すると、次のようになります。

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

andオペランドを右にシフトする代わりに、マスクを左にシフトすることもできます1。そのほうが理にかなっている）。ただし、良くも悪くも、アセンブリ言語 (この種の処理が通常行われる場所) では、マスクをレジスタにロードして必要に応じてシフトするよりも、オペランドをシフトしてマスクに定数を使用する方が通常は少し簡単です。and124

于 2013-09-29T15:06:32.070 に答える
1

これらは整数なので、整数にa / 2なります。が奇数の場合a、その整数は切り捨てられておりb、ループの次の繰り返しで半分、つまりループbの現在の繰り返しで 1 つが失われます ( b[ y] は毎回 2 倍になるため)。

于 2013-09-29T14:41:50.497 に答える
1

x が奇数の場合、xx = x/2を x/2 よりも 0.5 小さい値に設定します (整数除算により切り捨てられるため)。pできるように調整する必要があります。

于 2013-09-29T14:43:18.520 に答える
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 に答える