剑指offer四十八之不用加减乘除做加法

一、题目

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

二、思路

1、 采用位运算的方法,分三步:
  (1)、两个数异或:相当于每一位相加,而不考虑进位
  (2)、两个数相与,并左移一位:相当于求得进位
  (3)、重复步骤1和2,两个数相与的结果为0,和即为两个数异或的结果
2、例子演示:
 
3+11 = ?
 
13 的二进制      1 1 0 1                     -----a        13
11 的二进制      1 0 1 1                     -----b        11  
 (a&b)
<<1  ->
  1 0 0 1 0                 -----d         18
            a^b  ->     0 1 1 0               
   -----e          6
 (d&e)
<<1  ->
  0 0 1 0 0                 -----f         4
            d^e  ->  1 0 1 0 0              
   -----g        20
 (f&g)
<<1  ->
  0 1 0 0 0                ------h        8
            f^g  ->  1 0 0 0 0                 ------i
          16
 (h&i)
<<1  ->
  0 0 0 0 0

              ------h        0       ----
--------退出循环

            h^i  ->  1 1 0 0 0                ------i
          24
在第一步中,采用异或
第二步中,采用按位与,左移一位

三、代码

public class Solution {
public int Add(int num1,int num2) {
while( num2!=0 ){ //当进位等于0的时候,返回异或的结果,即是要求的和
int sum = num1 ^ num2; //两个数异或:相当于每一位相加,而不考虑进位
int carray = (num1 & num2) << 1;//两个数相与:并左移一位:相当于求得进位
num1 = sum;
num2 = carray;
}
return num1;
}
}

---------------------------------------------

参考链接:

https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215

上一篇:Server版Linux命令提示符揭秘


下一篇:Centos 6.5将光盘作为yum源的设置方法