題目#
leetcode 371 - Sum of Two Integers (題目說明請點連結)
題目簡述#
給兩個整數 a 和 b，請返回它們的和，但不能使用 + 和 - 運算符。
注意：這題要求我們使用位元運算來實現加法，這是一個經典的位元運算問題。
範例#
Example 1:
Input: a = 1, b = 2
Output: 3
Explanation: 1 + 2 = 3Example 2:
Input: a = 2, b = 3
Output: 5
Explanation: 2 + 3 = 5Example 3:
Input: a = -1, b = 1
Output: 0
Explanation: (-1) + 1 = 0解題思路#
這題要求我們在不使用 + 和 - 運算符的情況下計算兩個整數的和。我們可以使用位元運算（Bit Manipulation）來實現加法，具體方法是模擬二進位加法的過程。
解法#
位元運算法（Bit Manipulation Approach）
- 使用
XOR（^）運算來計算不進位的和 - 使用
AND（&）和左移運算來計算進位 - 重複上述過程直到沒有進位為止
- 最終結果就是不進位的和
步驟#
- 計算不進位的和：
- 使用
a ^ b計算不進位的和
- 使用
- 計算進位：
- 使用
(a & b) << 1計算進位
- 使用
- 更新變數：
- 將不進位的和賦值給
a - 將進位賦值給
b
- 將不進位的和賦值給
- 重複過程：
- 重複上述步驟直到
b為 0
- 重複上述步驟直到
- 返回結果：
- 返回
a，即最終的和
- 返回
例子說明#
a = 3, b = 5
| 步驟 | a | b | sum = a^b | carry = (a&b)«1 | 說明 |
|---|---|---|---|---|---|
| 初始化 | 3 (0011) | 5 (0101) | - | - | 開始計算 3 + 5 |
| 第 1 步 | 3 (0011) | 5 (0101) | 6 (0110) | 2 (0010) | sum = 3^5 = 6, carry = (3&5)«1 = 2 |
| 第 2 步 | 6 (0110) | 2 (0010) | 4 (0100) | 4 (0100) | sum = 6^2 = 4, carry = (6&2)«1 = 4 |
| 第 3 步 | 4 (0100) | 4 (0100) | 0 (0000) | 8 (1000) | sum = 4^4 = 0, carry = (4&4)«1 = 8 |
| 第 4 步 | 0 (0000) | 8 (1000) | 8 (1000) | 0 (0000) | sum = 0^8 = 8, carry = (0&8)«1 = 0 |
| 第 5 步 | 8 (1000) | 0 (0000) | - | - | b = 0，結束迴圈 |
最終結果： 8
二進位計算過程說明：
- 步驟 1：
3 (0011) + 5 (0101)- 不進位和：
0011 ^ 0101 = 0110 (6) - 進位：
(0011 & 0101) << 1 = 0001 << 1 = 0010 (2)
- 不進位和：
- 步驟 2：
6 (0110) + 2 (0010)- 不進位和：
0110 ^ 0010 = 0100 (4) - 進位：
(0110 & 0010) << 1 = 0010 << 1 = 0100 (4)
- 不進位和：
- 步驟 3：
4 (0100) + 4 (0100)- 不進位和：
0100 ^ 0100 = 0000 (0) - 進位：
(0100 & 0100) << 1 = 0100 << 1 = 1000 (8)
- 不進位和：
- 步驟 4：
0 (0000) + 8 (1000)- 不進位和：
0000 ^ 1000 = 1000 (8) - 進位：
(0000 & 1000) << 1 = 0000 << 1 = 0000 (0)
- 不進位和：
完整程式碼#
java
class Solution {
public int getSum(int a, int b) {
// 使用位元運算來實現加法
while(b != 0){
// 計算不進位的和
int sum = a ^ b;
// 計算進位
int carry = (a & b) << 1;
// 更新 a 為不進位的和
a = sum;
// 更新 b 為進位
b = carry;
}
// 返回最終結果
return a;
}
}時間複雜度#
- 時間複雜度：
O(1)，因為整數的位元數是固定的（32 位）- 最壞情況下需要處理所有位元的進位
- 但由於整數位元數固定，時間複雜度為常數
- 空間複雜度：
O(1)- 只使用了常數個變數來儲存中間結果
- 不需要額外的資料結構