《剑指offer》——不用加减乘除做加法

来源:转载

T:

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

不能用加减乘除做,只能求助于位运算啦。。

首先来看四个基本操作:

在整数的加法中,如果我们将两个加数num1, num2用二进制表示,有如下表示:

在二进制中,两个数相加,仔细琢磨,会发现有如下的规律:

  1. 如果对应的位上都为1,那么该位上就要归零,并且往左侧进一位
  2. 如果对应的位数不全都是11/0, 0/1, 0/0三种情况),那么该位在相加时,如果是1/0,或者0/1,就可置为1,如果是0/0,那就置为0。

好了,对于以上的两种规律,我们如何在其二进制上实现这种操作呢?

首先,通过上面的规律1,得到的是对应的进位位,可通过与(&)操作和左移(<<)操作实现;
其次,通过规律2得到的是非进位位,可通过异或(^)操作实现。

接着,如果将规律12中的结果再次进行一轮规律12的操作,又会得到两个结果,一个是非进位位对应的二进制,一个是进位位对应的二进制,然后可再接着下一轮……

那么,什么时候终止呢?就在进位位对应的二进制为0的时候,也就是说没有要进的位了,也就是相加结束了。

以上的思考,也是在经过别人代码的提示之后得到的,下附上代码。

code:

 package niuke.sward2offer.addWithoutOperates; /** * T:不用加减乘除做加法 * * 题目描述 * 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。 * * date:2-15.11.2 20:44 * @author SSS * */ public class Solution { public int Add(int num1, int num2) { int noCarryNum = num1 ^ num2; int carryNum = (num1 & num2) << 1; while (carryNum != 0) { num1 = noCarryNum; num2 = carryNum; noCarryNum = num1 ^ num2; carryNum = (num1 & num2) << 1; } return noCarryNum; } public static void main(String []args) { int num1 = 3; int num2 = 6; Solution solution = new Solution(); System.out.println(solution.Add(num1, num2)); } } 



分享给朋友:
您可能感兴趣的文章:
随机阅读: