【剑指Offer】048——不用加减乘除做加法（进制转化）

题目描述

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

解题思路

用位运算来实现。在这之前可以看看十进制是如何做的，如：5+7=12，第一步：相加各位的值，不算进位，得到2；第二步：计算进位值，得到10，如果第一步中的进位值为0，那么第一步得到的结果就是最终的结果；第三步：重复上述两步，只是相加的值变成上述两步得到的结果2和10。同样我们也可以使用这三步走的方式计算二进制值，5-0101，7-0111，那么就有第一步：相加各位的值（不算进位），得到0010，而这种操作相当于两个二进制数进行异或操作，即0101^{0111；第二步：计算进位值，得到1010，相当于两个二进制数各位做与操作得到0101，再向左移一位得到1010，即（0101&0111）<<1；第三步重复上述两步，各位相加(0010}1010)=1000，进位值为100=(010&1010)<<1。继续重复上述两步：1000^100=1100，进位值为0，跳出循环，1100为最终结果。

• step1: 进行异或运算，计算两个数各个位置上的相加，不考虑进位；
• step2: 进行位与运算，然后左移一位，计算进位值；
• step3: 把异或运算的结果赋给 num1，把进位值赋给 num2，依此循环，进位值为空的时候结束循环，num1就是两数之和。

参考代码

Java

public class Solution {
    public int Add(int num1, int num2) {
        if(num2 == 0)
            return num1;
        int sum = 0, carry = 0;
        while(num2 != 0){
            sum = num1 ^ num2;   // 不用进位的部分
            carry = (num1 & num2) << 1; // 进位部分
            num1 = sum;     // 更新num1
            num2 = carry;   // 更新num2
        }
        return num1;
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        return sum([num1,num2])

个人订阅号

image