【剑指Offer】T65 不用加减乘除实现加法

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

思路:以 87 + 15 = 102 为例

  • 正常加法拆分
    • 87 = 1010111(2),15 = 1111(2) 得到 102 = 1100110(2)
    • 不进位加法 1011000
    • 产生进位后的结果 0011100(作减法或者自己推导)
  • 使用二进制实现
    • 不进位的加法,显然就是 异或运算
    • 关键是求进位后的结果
    • 将上述两个结果相加,即可得到最终结果
    • 进位后结果 可以描述为:
      • 除了 1 加 1 都不会产生进位,可以想象成两个数先位与再左移一位(当前位置的 1 左移到进位的位置)。
      • 只有当两个数都为 1 的时候,位于结果为 1,其余为 0
      • 第一轮
        • 1010111 ^ 1111 = 1011000
        • (1010111 & 1111) << 1 = 0111 << 1 = 1110
      • 第二轮
        • 1011000 ^ 1110 = 1010110
        • (1011000 & 1110)<<1 = 10000
      • 第三轮
        • 1010110 ^ 10000 = 1000110
        • (1010110 & 10000)<<1 = 100000
      • 第四轮
        • 1000110 ^ 100000 = 1100110
        • (1000110 & 100000)<<1 = 0000
      • 跳出循环,结果为 1100110 + 0000 = 1100110

代码:

int Add(int num1, num2){
    int sum, carry;
    do{
        sum = num1 ^ num2;
        carry = (num1 & num2)<<1;
        num1 = sum;
        num2 = carry;
    }while(num2 != 0);
    return num2;
}

本文链接:https://ariser.cn/index.php/archives/402/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!