нужны разъяснения относительно этого цикла, выполняющего умножение

Question

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 

Я понимаю, что этот цикл находит произведение «а» и «б», используя алгебру:

а * Ь = (1/2) а * 2b

, но я не понимаю код:

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

Я надеялся, что кто-то может объяснить, почему «р» присваивается «р + y 'на нечетные значения x.

Answer 1

while (x > 0) { 
    if (x % 2 == 1) 
     p = p + y; 
    y = y*2; 
    x = x/2; 
} 

себе представить x = 4, у = 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, 4 = y, 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)

Answer 2

Поскольку это целые числа, a/2 будет целым числом. Если a нечетно, это целое число округлено вниз, и вы потеряете половину b в следующей итерации цикла, то есть одно целое b в текущей итерации цикла (так как b [y] удваивается каждый раз).

Answer 3

Если x нечетно, x = x/2 установит x на 0,5 меньше, чем x/2 (поскольку целочисленное деление округляет его). p необходимо настроить таким образом.

Answer 4

Подумайте о умножении в качестве повторного добавления, x * y добавляет y вместе x раз. Он также совпадает с добавлением 2 * y вместе x/2 раза. Концептуально несколько неясно, что это означает, если x нечетно. Например, если x = 5 и y = 3, что значит добавить в 2,5 раза? Код замечает, когда x нечетно, добавляет y in, тогда y = y * 2 и x = x/2. Когда x нечетно, это отбрасывает часть .5. Поэтому в этом примере вы добавляете y один раз, тогда x становится 2 (не 2,5), потому что целочисленное деление отбрасывает фракцию.

В конце каждого цикла вы увидите, что произведение исходных x и y равно p + x * y для текущих значений p, x и y. Цикл повторяется до тех пор, пока x не станет 0, и результат полностью будет равен p.

Он также помогает видеть, что происходит, если вы делаете таблицу и каждый раз обновляете ее через цикл. Эти значения в начале каждой итерации:

x | y | p 
---------- 
5 | 3 | 0 
2 | 6 | 3 
1 | 12 | 3 
0 | 24 | 15 

Answer 5

Это работает, наблюдая, что (например) 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 ИНГ с 1, мы бы and с 1, затем с 2, затем с 4 и т. д. (на самом деле, вероятно, это было бы гораздо более ощутимым образом).Однако, к лучшему или к худшему, на языке ассемблера (где обычно это делается вообще) обычно легче перемещать операнд и использовать константу для маски, чем загружать маску в регистр и при необходимости менять ее.

Answer 6

Вы должны переписать 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.