位运算03 不用加号的加法[C++]

图源：文心一言

上机题目练习整理，位运算，供小伙伴们参考~🥝🥝

网页版目录在页面的右上角↗~🥝🥝

第1版：在力扣新手村刷题的记录~🧩🧩

编辑：梅头脑🌸

审核：文心一言

题目：面试题 17.01. 不用加号的加法 - 力扣（LeetCode）

🧵面试题 17.01. 不用加号的加法

🧩题目

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:
输入: a = 1, b = 1
输出: 2
提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

🌰解题一：循环+按位运算（一）

📇算法思路

算法思想：

初始化：函数接收两个整数a和b作为输入。

循环条件：当进位b不为0时，循环继续。

计算进位：使用a & b来计算a和b的哪些位都需要进位（仅当 a 为 1，且 b 为 1时，需要进位）。然后，通过左移一位（<< 1）来将这些进位应用到正确的位置上。这里使用unsigned int是为了确保左移操作不会引入任何符号位。

计算本位和：使用a ^ b（异或操作）来计算不考虑进位时的和。异或操作会返回在两个输入中只有一个为1的那些位上设置1的结果，例如：

a = 1， b = 1 ，算数运算：a + b = 10，位运算：本位和为 1 ^ 1 = 0，进位为 1 & 1 = 1；

a = 1， b = 0 ，算数运算：a + b = 01，位运算：本位和为 1 ^ 0 = 1，进位为 1 & 0 = 0；

a = 0， b = 1 ，算数运算：a + b = 01，位运算：本位和为 0 ^ 1 = 1，进位为 0 & 1 = 0；

a = 0， b = 0 ，算数运算：a + b = 00，位运算：本位和为 0 ^ 0 = 0，进位为 0 & 0 = 0；

更新操作数：

a被更新为不考虑进位的本位和（a ^ b的结果）。
b被更新为进位（(unsigned int)(a & b) << 1的结果）。这样，在下一次循环中，b将包含所有需要被加到a上的进位。

返回结果：当b变为0（即没有更多的进位需要处理）时，循环结束，函数返回a作为最终的和。

时间复杂度：O(1)或O(log(max(a, b)))；我们可以认为时间复杂度是O(1)，其中1表示一个固定的上限，即整数的大小，或整数的二进制表示的长度。
空间复杂度：O(1)；

⌨️算法代码

#include <iostream>
#include <bitset>
using namespace std;

class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

//class Solution {
//public:
//    int add(int a, int b) {
//        cout << "a = " << a << " = " << bitset<32>(a) << ", b = " << b << " = " << bitset<32>(b) << endl;
//
//        while (b != 0) {
//            unsigned int carry = (unsigned int)(a & b) << 1;
//            cout << "carry = " << bitset<32>(carry);
//            a = a ^ b;
//            cout << ", a = " << bitset<32>(a);
//            b = carry;
//            cout << ", b = " << bitset<32>(b) << endl;
//        }
//        return a;
//    }
//};
//
//int main()
//{   
//    int a = 111;  int b = 899;
//    Solution solution;
//    int result = solution.add(a, b);
//    cout << "result = " << result << " = " << bitset<32>(result) << endl;
//
//    return 0;
//}

作者：力扣官方题解
链接：https://leetcode.cn/problems/add-without-plus-lcci/solutions/1718025/bu-yong-jia-hao-de-jia-fa-by-leetcode-so-pp8a/

📇执行结果

输入 a = 111， b = 899后，执行结果如下：

📇代码解释

1：输入 a 与 b

a = 111（十进制） = 00000000000000000000000001101111（二进制）
b = 899（十进制） = 00000000000000000000001110000011（二进制）
本轮需要进位的在第0位、第1位，11 + 11 = 110；

2：计算第1轮本位和与进位

进位 carry ：a & b = 00000000000000000000000000000011，无符号数算数左移1位结果为 000000000000000000000000000000110；
本位和 a : a ^ b = 00000000000000000000001111101100；
进位 b：b = carry = 000000000000000000000000000000110；
本轮需要进位的在第2位，100 + 100 = 1000；

3：计算第2轮本位和与进位

进位 carry ：a & b = 00000000000000000000000000000100，无符号数算数左移1位结果为 00000000000000000000000000001000；
本位和 a : a ^ b = 00000000000000000000001111101010；
进位 b：b = carry = 00000000000000000000000000001000；
本轮需要进位的在第3位，1000 + 1000 = 10000；

4：计算第3轮本位和与进位

进位 carry ：a & b = 00000000000000000000000000001000，无符号数算数左移1位结果为 00000000000000000000000000010000；
本位和 a : a ^ b = 00000000000000000000001111100010；
进位 b：b = carry = 00000000000000000000000000010000；
本轮 a 与 b 没有同时为 1 的位，最后进行异或，进位b更新为0，本位和a即为答案；

5：计算第4轮本位和与进位

进位 carry ：a & b = 00000000000000000000000000000000，无符号数算数左移1位结果为 00000000000000000000000000000000；
本位和 a : a ^ b = 00000000000000000000001111110010；
进位 b：b = carry = 00000000000000000000000000000000；
返回：a = 1010 (十进制) = 00000000000000000000001111110010（二进制）；

这道题目的难点应该是从后向前一轮一轮地处理进位，（本位和异或就可以搞定了），感觉官方的解法真的很简洁美观，但是以我的功底，要能自己写出这种水平的代码，感觉至少还要1年，囧...

🌰解题二：循环+按位运算（二）（简单全加器原理）

📇算法思路

算法思想：

初始化：函数接收两个整数a和b作为输入。

循环条件：int 通常为 32位，未读取完32位时，循环继续遍历读取每1位。

全加器逻辑：

每次从a和b中提取一位（从最低位开始）记入 bita、bitb进行运算，调用函数fulladder计算本位和 sum 与进位 carryout，计算结果存入容器 adderresult。

计算进位：使用a & b来计算a和b的哪些位都需要进位（仅当 a 为 1，且 b 为 1时，需要进位）。然后，通过左移一位（<< 1）来将这些进位应用到正确的位置上。这里使用unsigned int是为了确保左移操作不会引入任何符号位。

计算本位和：使用 sum = a ^ b（异或操作）来计算不考虑进位时的和。异或操作会返回在两个输入中只有一个为1的那些位上设置1的结果；

更新操作数：在result 中输出本位和与进位；

返回结果：当int遍历结束时时，循环结束，函数返回result作为最终的和。

时间复杂度：O(1)：总是处理32位整数；
空间复杂度：O(1)：使用了固定数量的变量来存储中间结果和进位；

⌨️算法代码

#include <iostream>  
#include <utility> // 为了使用 std::pair  

// 全加器函数，返回一个包含和与进位的pair  
std::pair<int, int> fulladder(int a, int b, int carryin) {
    int sum = a ^ b ^ carryin; // 不考虑进位的和  
    int carryout = (a & b) | ((a ^ b) & carryin); // 进位，注意这里修正了逻辑错误  
    return std::make_pair(sum, carryout); // 返回和与进位的pair  
}

// 两个32位整数相加  
int add(int a, int b) {
    int carry = 0; // 初始化进位为0  
    int result = 0; // 初始化结果为0  
    for (int i = 0; i < 32; ++i) { // 逐位相加  
        int bita = (a >> i) & 1; // a的第i位  
        int bitb = (b >> i) & 1; // b的第i位  
        // 调用全加器并更新结果和进位  
        std::pair<int, int> adderresult = fulladder(bita, bitb, carry);
        result |= adderresult.first << i; // 将当前位的和加入结果中  
        carry = adderresult.second; // 更新进位为全加器的进位输出  
    }
    // 注意：此实现不处理溢出情况。在实际应用中，应考虑溢出。  
    return result;
}

int main() {
    int a = 111; // 101 in binary, 但实际上在32位整数中是 0000 ... 0101  
    int b = 899; // 011 in binary, 但实际上在32位整数中是 0000 ... 0011  
    int expected = 1010; // 1000 in binary, 但实际上在32位整数中是 0000 ... 1000  
    int actual = add(a, b); // 应该返回1010（没有溢出的情况下）  
    std::cout << "expected: " << expected << std::endl; // 输出期望结果  
    std::cout << "actual: " << actual << std::endl; // 输出实际结果，应该是8  
    return 0; // 程序成功执行完毕，返回0表示成功状态码  
}

作者：文心一言

📇执行结果

测试代码

int add(int a, int b) {
    int carry = 0;
    int result = 0;
    for (int i = 0; i < 32; ++i) {
        int bita = (a >> i) & 1;
        int bitb = (b >> i) & 1;

        std::pair<int, int> adderresult = fulladder(bita, bitb, carry);

        // 添加打印语句来查看中间变量的值  
        std::cout << "Iteration（位数） " << i << ":" << std::endl;
        std::cout << "  bita: " << bita << std::endl;
        std::cout << "  bitb: " << bitb << std::endl;
        std::cout << "  carry（本轮进位）: " << carry << std::endl;
        std::cout << "  adderresult (sum, carry): ("
            << adderresult.first << ", " << adderresult.second << ")" << std::endl;

        result |= adderresult.first << i;
        carry = adderresult.second;

        // 打印当前的结果和进位  
        std::cout << "  result: " << result << " = " << std::bitset<32>(result) <<std::endl;
        std::cout << "  carry（下轮进位）: " << carry << std::endl;
        std::cout << std::endl; // 打印空行以便于阅读  
    }
    return result;
}

运行结果

1：输入 a 与 b

a = 111（十进制） = 00000000000000000000000001101111
b = 899（十进制） = 00000000000000000000001110000011

2：代码运行

Iteration（位数） 0:
bita: 1
bitb: 1
carry（本轮进位）: 0
adderresult (sum, carry): (0, 1)
result: 0 = 00000000000000000000000000000000
carry（下轮进位）: 1

Iteration（位数） 1:
bita: 1
bitb: 1
carry（本轮进位）: 1
adderresult (sum, carry): (1, 1)
result: 2 = 00000000000000000000000000000010
carry（下轮进位）: 1

Iteration（位数） 2:
bita: 1
bitb: 0
carry（本轮进位）: 1
adderresult (sum, carry): (0, 1)
result: 2 = 00000000000000000000000000000010
carry（下轮进位）: 1

Iteration（位数） 3:
bita: 1
bitb: 0
carry（本轮进位）: 1
adderresult (sum, carry): (0, 1)
result: 2 = 00000000000000000000000000000010
carry（下轮进位）: 1

Iteration（位数） 4:
bita: 0
bitb: 0
carry（本轮进位）: 1
adderresult (sum, carry): (1, 0)
result: 18 = 00000000000000000000000000010010
carry（下轮进位）: 0

Iteration（位数） 5:
bita: 1
bitb: 0
carry（本轮进位）: 0
adderresult (sum, carry): (1, 0)
result: 50 = 00000000000000000000000000110010
carry（下轮进位）: 0

Iteration（位数） 6:
bita: 1
bitb: 0
carry（本轮进位）: 0
adderresult (sum, carry): (1, 0)
result: 114 = 00000000000000000000000001110010
carry（下轮进位）: 0

Iteration（位数） 7:
bita: 0
bitb: 1
carry（本轮进位）: 0
adderresult (sum, carry): (1, 0)
result: 242 = 00000000000000000000000011110010
carry（下轮进位）: 0

Iteration（位数） 8:
bita: 0
bitb: 1
carry（本轮进位）: 0
adderresult (sum, carry): (1, 0)
result: 498 = 00000000000000000000000111110010
carry（下轮进位）: 0

Iteration（位数） 9:
bita: 0
bitb: 1
carry（本轮进位）: 0
adderresult (sum, carry): (1, 0)
result: 1010 = 00000000000000000000001111110010
carry（下轮进位）: 0

……

Iteration（位数） 31:
bita: 0
bitb: 0
carry（本轮进位）: 0
adderresult (sum, carry): (0, 0)
result: 1010 = 00000000000000000000001111110010
carry（下轮进位）: 0

expected: 1010
actual: 1010

🌰自留错误版本

📇算法思路

基本思想同算法一，通过计算本位和与进位计算结果~

⌨️算法代码（错误，自留代码）

#include <iostream>
#include <bitset>
using namespace std;

class Solution {
public:

    //代码逻辑有问题， sum += 那一行，违背了位运算原则。
    int add(int a, int b) {
        int sum = 0;
        int carry = 0;
        int i = 0;
        for (i = 0; i < 32; i++) {
            cout << "本轮 i = " << i << endl;
            int bitA = (a >> i) & 1;
            cout << "本轮 bitA = " << bitA << endl;
            int bitB = (b >> i) & 1;
            cout << "本轮 bitB = " << bitB << endl;
            int bitSum = bitA ^ bitB;
            cout << "本轮 bitSum = " << bitSum << endl;
            carry = (bitA & bitB) | (bitSum & carry);
            cout << "本轮 carry = " << carry << endl;
            sum = sum + (carry << i + 1) + (bitSum << i);
            cout << "本轮 sum = " << sum << endl;
            carry <<= 1;
            cout << "carry 左移一位" << endl;
            cout << endl;
        }
        return sum;
    }

    //int add(int a, int b) {
    //    int result = 0;
    //    int carry = 0;
    //    int i = 0;
    //    for (i = 0; i < 32; i++) {
    //        cout << "本轮 i = " << i << endl;
    //        int bitA = (a >> i) & 1;
    //        cout << "本轮 bitA = " << bitA << endl;
    //        int bitB = (b >> i) & 1;
    //        cout << "本轮 bitB = " << bitB << endl;
    //        int bitSum = bitA ^ bitB;
    //        cout << "本轮 bitSum = " << bitSum << endl;
    //        carry = (bitA & bitB) | (bitSum & carry);
    //        cout << "本轮 carry = " << carry << endl;
    //        // sum = sum + (carry << i + 1) + (bitSum << i);
    //        result = result | bitSum << i;
    //        if (carry & 1) { result |= (1 << (i + 1));}
    //        cout << "本轮 result = " << result << endl;
    //        carry >>= 1;
    //        cout << "carry 右移一位" << endl;
    //        cout << endl;
    //    }
    //    return result;
    //}

};

int main()
{   
    //int a = 1;  int b = 1;
    int a = 111;  int b = 899;
    Solution solution;
    int result = solution.add(a, b);
    cout << result;
    return 0;
}

作者：梅头脑

这个解法呃，倒是可以运行，将本位和与进位和分开了，接近解法二的思路。但是因为没能很好得处理进位的问题，就使用了加法企图蒙混过关 sum = sum + (carry << i + 1) + (bitSum << i); （此处如果使用 “ | ” 会吞掉进位与本位的相同位），违背了题目不能使用加法的本意。又想到使用result，也出现了类似的问题，后来摆脱文心一言用全加器的原理修改掉，也就是解法二~~