e253 - a + b problem

🔗 前往 ZeroJudge 原題

題目描述

題目要求在不使用加法、減法、乘法或除法運算子的情況下，計算兩個整數的和。

解題思路

此題的核心在於使用位元運算來模擬加法的過程。加法可以分解為兩個步驟：

1. 計算兩個數的異或 (XOR)，得到不考慮進位的和。
2. 計算兩個數的與 (AND)，然後左移一位，得到進位。 將上述兩個步驟重複進行，直到進位為 0，則異或的結果即為最終的和。

複雜度分析

• 時間複雜度: O(log(max(a, b)))，因為 while 迴圈的次數取決於進位的位數，而進位的位數與 a 和 b 的大小有關。
• 空間複雜度: O(1)，因為只使用了常數個額外的變數。

程式碼

#include <stdio.h>
int add(int a, int b) {
    while(b) {
        int ta = a ^ b, tb = (a & b) << 1;
        a = ta, b = tb;
    }
    return a;
}
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d", add(a, b));
    return 0;
}