ضرب دو عدد صحیح با استفاده از اپراتورهای بیتی

روش‌های مختلفی برای ضرب اعداد صحیح وجود دارد. یک روش جالب الگوریتم دهقان روسی (Russian Peasant Algorithm) است. این الگوریتم بدین صورت است که:

حاصل ضرب n1 × n2 برابر می‌شود با:
اگر n2 یک عدد فرد باشد، آنگاه n1 را یادداشت می‌کنیم و اگر زوج باشد، از آن صرف نظر می‌کنیم. سپس n1 را دو برابر و n2 را نصف می‌کنیم. مجدد بررسی می‌کنیم که: اگر n2 یک عدد فرد باشد، آنگاه n1 را یادداشت کنیم و اگر زوج باشد، از آن صرف نظر کنیم. این کار را تا زمانی که n2 برابر صفر نشده، ادامه می‌دهیم. در آخر، اعداد یادداشت شده را با هم جمع می‌کنیم و نتیجه برابر n1 × n2 می‌باشد.

حاصل ضرب 10 × 39:

n1:   n2:
39    10  ---> 10 is even
78    5   ---> 5  is odd   ---> 78
156   2   ---> 2  is even
312   1   ---> 1  is odd   ---> 312
624   0
                               -----
                                390

حاصل ضرب 11 × 39:

n1:   n2:
39    11  ---> 11 is odd   ---> 39
78    5   ---> 5  is odd   ---> 78
156   2   ---> 2  is even
312   1   ---> 1  is odd   ---> 312
624   0
                               -----
                                429

قبلا در این صفحه، دربارهٔ نحوهٔ جمع و تفریق بین دو عدد صحیح با استفاده از اپراتورهای بیتی توضیحاتی داده شده بود. در زیر، دربارهٔ ضرب این اعداد با استفاده از اپراتورهای بیتی توضیحاتی داده می‌شود. به تابع mul موجود در کد زیر دقت کنید:

#include <stdio.h>

int mul(int, int);
int mul_recursive(int, int);

int main()
{
    printf("%d\n", mul(39, 10));
    printf("%d\n", mul(39, 11));
    printf("%d\n", mul_recursive(39, 10));
    printf("%d\n", mul_recursive(39, 11));

    return 0;
}

int mul(int n1, int n2)
{
    int res = 0;

    while(n2)
    {
        if(n2 & 1)
            res += n1;
        n1 <<= 1;
        n2 >>= 1;
    }
    return res;
}

// Following is the recursive implementation for the same approach.
int mul_recursive(int n1, int n2)
{
    if(!n2)
        return 0;
    if(n2 == 1)
        return n1;

    int res = 0;

    if(n2 & 1)
        res += n1;
    return res + mul_recursive(n1 << 1, n2 >> 1);
}

در کد بالا از الگوریتم دهقان روسی (Russian Peasant Algorithm) جهت ضرب استفاده شده است. تابع mul موجود در کد بالا بصورت زیر عمل می‌کند:

۱. متغیر res برابر صفر قرار داده می‌شود.
۲. تا زمانی که n2 برابر صفر نباشد:
الف) اگر n2 یک عدد فرد باشد، آنگاه n1 به res اضافه می‌شود.
ب) n1 دو برابر و n2 نصف می‌شود.
۳. مقدار res بازگشت داده می‌شود.

39 * 10:

     100111         39
   x   1010       x 10
  ---------
     000000      (39 * 1)
    1001110       39 * 2
   00000000      (39 * 4)
  100111000       39 * 8
  ---------      ---------
  110000110       39 * 10

39 * 11:

     100111         39
   x   1011       x 11
  ---------
     100111       39 * 1
    1001110       39 * 2
   00000000      (39 * 4)
  100111000       39 * 8
  ---------      ---------
  110101101       39 * 11

تابع mul_recursive، پیاده‌سازی بازگشتی تابع mul، جهت approach مشابه می‌باشد.

MD5 checksum:
615d975bbf0977083e269fb25970584d *multiply_bitwise_operators.zip