جمع و تفریق دو عدد صحیح با استفاده از اپراتورهای بیتی

کد زیر جمع بین دو عدد صحیح را با استفاده از اپراتورهای بیتی بدست می‌آورد. به این کد دقت کنید:

#include <stdio.h>

int sum(int, int);

int main()
{
    printf("%d\n", sum(5, 4));

    return 0;
}

int sum(int n1, int n2)
{
    // Iterate till there is no carry
    while(n2)
    {
        int carry = n1 & n2;
        n1 = n1 ^ n2;
        n2 = carry << 1;
    }
    return n1;
}

Output:

9

در کد بالا اپراتور XOR جمع بین دو بیت را به ما می‌دهد. هدف از XOR، انجام کارهای زیر است:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0  // (Carry will be generated by AND)

با استفاده از اپراتور AND می‌توان بیت Carry را بدست آورد. در واقع اگر دو بیت را با هم AND کنیم، بیت Carry بدست می‌آید. هدف از AND، انجام کار زیر است:

1 + 1 = 0  // Generates carry (1)

اگر Carry ساخته شود این حلقه تکرار می‌شود، تا مقدار آن (Carry) به n1 اضافه شود. این Carry بیت به بیت به سمت چپ Shift داده می‌شود تا در چرخش بعدی به n1 اضافه شود. زمانیکه Carryای وجود نداشته باشد، حلقه چرخهٔ بعدی خود را نخواهد دید و مقدار بازگشتی تابع n1 خواهد بود.

پیاده‌سازی بازگشتی تابع sum، جهت approach مشابه:

// Following is the recursive implementation for the same approach.
int sum(int n1, int n2)
{
    if(n2)
        return sum(n1 ^ n2, (n1 & n2) << 1);
    return n1;
}

الگوریتم تفریق نیز مشابه با جمع می‌باشد. در فایل‌های زیر، تابع جمع و تابع تفریق به هر دو روش (حلقه و بازگشت) نوشته شده است.

MD5 checksums:
47aa4f29464598f81a9012da22f8abb4 *sum_bitwise_operators.zip
e37c52f23b83ba93f23efbdc54a999b2 *sum_bitwise_operators_recursive.zip
afd7315098a25291cd596c187ab51ac2 *sub_bitwise_operators.zip
dbf21a539ff55f83ab5db1ead385a96f *sub_bitwise_operators_recursive.zip