剑指offer—不用加减乘除做加法 解答

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

题目描述

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

思路

位运算

  • 方法1,通过与操作和或操作获取两位相加结果,设置标志位来获取进位输出,使用StringBuffer保存结果

使用变量flag作为进位标志,当flag = 1时,表示接收到进位输出,需要进行进位;使用StringBuffer作为结果接收,调用append方法把每一位保存进去,因为我们使用从右往左移位的,所以我们需要从后往前输出StringBuffer,所以需要进行一次翻转,然后转换为10进制整数输出。

每一位相加一共有一种可能:

1.01相加,该位为1,进位为0

2.10相加,该位为1,进位为0

3.11相加,该位为0,进位为1

4.00相加,该位为0,进位为0

流程:

  1. 初始化StringBuffer,设置进位标志为0(不进位)
  2. 对num1和num2循环右移判断(循环退出条件为num1和num2均为0并且进位标志为0)
  3. 如果为01或者10相加,判断进位标志
    1. 如果进位标志为1,执行append('0'),并且保存进位标志为1
    2. 如果进位标志为0,执行append('1'),并且设置进位标志为0(不进位)
  4. 如果为00或者11相加,判断进位标志
    1. 如果进位标志为0,判断是11相加还是00相加
      1. 如果是11相加,执行append('0'),并且设置进位标志为1
      2. 如果是00相加,执行append('0'),保持进位标志为0,
    2. 如果进位标志为1,判断是11相加还是00相加
      1. 如果是11相加,执行append('1'),并且保持进位标志为1
      2. 如果是00相加,执行append('1'),并且把进位标志设置为0
  5. 翻转Stringbuffer并且转为10进制整数
  • 方法2,依然通过位运算,使用异或获取进位前的和,使用逻辑与操作来获取进位,获取到进位后左移一位作为进位

第一步:先计算二进制相加的值(取异或),不考虑进位;

第二部:计算进位的值(与,都为1进位),左移一位作为进位的数

第三部:重复上两部,各位相加,直到进位制为0,跳出循环

例如:

计算3+4 3(11) 4(100)

  1. 计算异或,11^100=011
  2. 计算进位,11&100=010 左移一位 0100
  3. 拿上一次进位的值和不进位的相加的值异或 得到0111
  4. 进位值为0,输出0111

代码

public int add(int num1 ,int num2){
        StringBuffer sb = new StringBuffer("");
        int n1 = num1;
        int n2 = num2;
        int flag = 0;
        while(n1!=0||n2!=0||flag==1){
            //01/10相加
            if(((n1&1)^(n2&1))==1){
                if(flag==1) //进位
                    sb.append('0');
                else
                    sb.append('1');
            }else{
                if(flag==1){
                    sb.append('1');
                    if((n1&1)==0&&(n2&1)==0)//如果为00相加,不需要进位,反之保持进位标志为1(11相加需要进位)
                        flag = 0;
                }else 
                    if((n1&1)==1||(n2&1)==1)
                        sb.append('0');
                        flag = 1;
                    else sb.append('0');
            }
            n1 = n1>>1;
            n2 = n2>>1;
        }
        StringBuffer str = sb.reverse();
        return Integer.parseInt(str.toString(),2);
    }
  • 更简单的方式
public int Add(int num1,int num2) {
        while (num2!=0) {
            int temp = num1^num2;
            num2 = (num1&num2)<<1;
            num1 = temp;
        }
        return num1;
    }
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/add-by-numbit.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!