Cộng 2 số nguyên bằng phép toán bitwise đệ quy trong C

Cộng 2 số nguyên không dùng toán tử +, chỉ dùng phép XOR, AND, dịch bit. Dựa trên logic Half Adder.

Nguyên lý

• Tổng không nhớ: a ^ b (XOR)
• Nhớ (carry): (a & b) << 1 (AND rồi dịch trái 1)
• Lặp lại với a = carry, b = sum cho đến khi carry = 0

Ví dụ

54 + 897 = 951

Chương trình mẫu

#include <stdio.h>

int addNumbers(int a, int b) {
    int carry = (a & b) << 1;
    int result = a ^ b;
    if (carry == 0)
        return result;
    else
        return addNumbers(carry, result);
}

int main() {
    int a = 54, b = 897;
    printf("Tổng %d + %d = %d", a, b, addNumbers(a, b));
    return 0;
}

Kết quả

Tổng 54 + 897 = 951

Lưu ý: Đây là minh họa nguyên lý mạch Half Adder. Trong thực tế dùng toán tử + hiệu quả hơn.