【剑指offer】不用加减乘除做加法

考察知识点：位运算

题目描述

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

题解

解法一：累加累减

分析

不能用 +、-、*、/，我用 ++ 和 – 总行吧?
当 num2 为负数，对 num1-- ，累减次数为 num2 的绝对值
当 num2 为正数，对 num1++，累加次数为 num2 的值

代码

class Solution {
public:
    int Add(int num1, int num2)
    {
        if(num2<0){
            for(int i=num2;i<0;i++)
                num1--;
            return num1;
        }else{
            for(int i=0;i<num2;i++)
                num1++;
            return num1;
            }
    }
};

解法二：位运算

分析

先来回忆一下五种常用的位运算符：

1. &，与运算，参与运算的两者都为 1 时，结果才为 1，否则为 0
2. |，或运算，参与运算的两者都为 0 时，结果才为 0，否则为 1
3. ^，异或运算，参与运算的两者同为 1 或者同为 0 时，结果为 1，否则为 0
4. <<，左移运算，如 A<<B，即对 A * 2 <math> <semantics> <mrow> <msup> <mi> B </mi> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> ^B </annotation> </semantics> </math>B
5. >>，右移运算，如 A>>B，即对 A / 2 <math> <semantics> <mrow> <msup> <mi> B </mi> </msup> </mrow> <annotation encoding="application&#47;x&#45;tex"> ^B </annotation> </semantics> </math>B

具体运算步骤：

1. 两个数异或，相当于每一位相加，不考虑进位
2. 两个数与运算，并左移一位，相当于求得进位
3. 将上述两步结果相加
4. 由于可能会产生新的进位，所以不断重复 1-3 步骤，直到进位为 0

代码

class Solution {
public:
    int Add(int num1, int num2)
    {
        while(num2){
            int temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
};