原创

【剑指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])
正文到此结束
本文目录