⭐ 题目日期：

虾皮 - 2024/10/26

🕵🏽 面试评估：

这道题主要考察位运算基础，要求候选人掌握位运算的核心概念，包括按位与 (&)、异或 (^)、左移 (<<) 的性质以及如何通过位运算实现加法的逻辑：异或计算无进位加法，与加左移计算进位。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

在计算机中，数字由 0 和 1 组成。用位运算实现加法有四种可能组合：

1. 0 + 0 = 00
2. 0 + 1 = 01
3. 1 + 0 = 01
4. 1 + 1 = 10

我们发现只有 1 和 1 相加才产生进位，可以用与(&) 来计算进位，而其他三种组合的运算结果都符合异或的运算规则，相同为 0，不同为 1。

因此用位运算来计算两数(a, b)相加可以拆分为两个步骤：

1. 计算两数无进位加法，得到结果 X
2. 计算两数进位，由于进位的“效应”需要在下一位才能实现，需将结果左移，得到结果 Y

若进位 Y 为 0， 则返回最终的结果 X；

若进位 Y 不为 0， 则要继续计算 X + Y, 令 a = X, b = Y, 又可以重复利用程序进行两数之和的计算，直到进位为 0，计算完成。

💻代码：

Java

public int add(int a, int b) {
    while (b != 0) {
        // 计算进位
        int carry = (a & b) << 1; 
        
        // 计算无进位加法
        a = a ^ b;  
        
        // // 更新进位              
        b = carry;                
    }
    
    return a;
}

Python

def add(a: int, b: int) -> int:
    while b != 0:
        # 计算进位
        carry = (a & b) << 1
        # 计算无进位加法
        a = a ^ b
        # 更新进位
        b = carry
    return a

C++

class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            // 计算进位
            int carry = (a & b) << 1;
    
            // 计算无进位加法
            a = a ^ b;
    
            // 更新进位
            b = carry;
        }
    
        return a;
    }
};

🚵🏻复杂度分析：

时间复杂度：O(1), 在最坏情况下，while 循环至多跑 32 次，循环内部的操作为 O(1), 总的时间复杂度为 O(1)

空间复杂度：O(1)