【剑指Offer】48、不用加减乘除做加法

题目描述：

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

解题思路：

本题同样是对发散思维能力的一个考察。首先，我们需要考虑是要求和却不能使用四则运算，那么还能用什么呢？除了四则运算以外，还可以进行计算的也就只剩下了位运算。因此，需要进一步考虑二进制数的位运算，用位运算来代替加法。

具体思路是：三步走策略。第一步，不考虑进位对每一位相加（模2和），也就是0+0=0,1+1=0，0+1=1,1+0=0，不难看出这一步其实就是做异或运算。第二步，考虑进位，只有1+1会产生进位，因此求每一位的进位可以先将两个数做与运算，然后再左移一位。第三步，将前面两个结果相加，相当于递归相加，直到不产生进位为止。

编程实现（Java）：

public class Solution {

    /*

        思路：用位运算代替加法

        三步走：第一步：不考虑进位加 第二位：考虑进位 第三步：原结果加上进位

    */

    public int Add(int num1,int num2) {

        //非递归实现

        int sum=0,carry=1;

        while(carry!=0){ //进位不等于0就循环加

            sum=num1^num2;

            carry=(num1&num2)<<1;

            num1=sum;

            num2=carry;

        }

        return num1;

    }

    public int Add(int num1,int num2) {

        //递归实现

        if(num2==0)

            return num1;

        int sum=num1^num2;

        int carry=(num1&num2)<<1;

        return Add(sum,carry);

    }

}

相关问题：

不使用新的变量，交换两个变量的值。

巴特西

【剑指Offer】48、不用加减乘除做加法

最新文章

热门文章