剑指65：不用加减乘除做加法

传送门

nowcoder
leetcode

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 +、-、*、/四则运算符号。

C++ 代码 - nowcoder

/*
    1.两个数异或：等价于每一位相加，而不考虑进位。
    2.两个数相与，并左移一位：等价于求出进位。
    3.将上述两步的结果相加。

    递归会终止的原因：
        (a & b) << 1 最右边会多一个 0
        继续递归，0 慢慢增多，
        最后进位变为 0，递归终止。
*/
class Solution {
public:
    int Add(int num1, int num2) {
        while (num2 != 0) {
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }

        return num1;
    }
};

C++ 代码 - leetcode

/*
    十进制加法中先把每一位对齐，然后每一位相加，和大于等于 10 则下一位进一。
    二进制的加法运算和十进制类似，也是每一位相加，和大于等于 2 则进一，
    二进制数求和及进位的操作：位运算来实现。
    
    异或运算 ^ 的结果为对应位相加，
    运算 & 的结果左移一位为进位的结果。
*/
class Solution {
public:
    int encryptionCalculate(int a, int b) {
        if (a == 0 || b == 0) {
            return a == 0 ? b : a;
        }
        // 设 a = 1001，b = 0101
        // 求和 1100
        int sum = a ^ b;
        // 进位 0001 << 1 = 0010
        int carry = (a & b) << 1;
        return encryptionCalculate(sum, carry);
    }
};