程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2023-06(2)

【剑指Offer】个人学习笔记_65_不用加减乘除做加法

发布于2021-05-29 19:32     阅读(1358)     评论(0)     点赞(19)     收藏(5)


刷题日期:下午7:44 2021年5月27日星期四

个人刷题记录,代码收集,来源皆为leetcode

经过多方讨论和请教,现在打算往Java方向发力

主要答题语言为Java

题目:

剑指 Offer 65. 不用加减乘除做加法

难度简单176

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

示例:

输入: a = 1, b = 1
输出: 2

提示:

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

题目分析

也就是++也用不了,要么采用位运算,要么就得挨个数了。

端粒L1 2020-02-15

这题位运算还是背下来吧,毕竟位运算这种模拟加法用法基本就这题,很容易就忘掉。。。。。

^ 亦或 ----相当于 无进位的求和, 想象10进制下的模拟情况:(如:19+1=20;无进位求和就是10,而非20;因为它不管进位情况)

& 与 ----相当于求每位的进位数, 先看定义:1&1=1;1&0=0;0&0=0;即都为1的时候才为1,正好可以模拟进位数的情况,还是想象10进制下模拟情况:(9+1=10,如果是用&的思路来处理,则9+1得到的进位数为1,而不是10,所以要用<<1向左再移动一位,这样就变为10了);

这样公式就是:(a^b) ^ ((a&b)<<1) 即:每次无进位求 + 每次得到的进位数--------我们需要不断重复这个过程,直到进位数为0为止;

初始解答:

学习了K神下面评论大佬的方式。

class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        // 转换成非进位和 + 进位
        return add(a ^ b, (a & b) << 1);
    }
}

执行结果:通过

显示详情 添加备注

执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗:35.4 MB, 在所有 Java 提交中击败了21.54%的用户

学习他人:

方法一:

russwest44L1 2020-06-06

本题a+b的难点在于: 1、不用加法时,其和还可以用什么表示 2、进位怎么表示,非进位和怎么表示 3、既然结果是进位+非进位和,但这里又他奶奶的又用到了加法,这又该怎么办

答: 1、a+b的和还可以用 进位+非进位和,比如6+7 传统意义上的进位是1,但这里所说的进位和传统意义上的进位是不同的(不知道你有没有懂?如果不懂,别慌,先跳过这里,去看下面第二个问题的回答)

2、 进位可以用 a&b<<1 表示,非进位和用 a^b(异或)表示,这里为什么是这样,可以把a和b用二进制表示,然后举几个例子验证一下就OK了,验证的结果肯定是 a+b的和 = a^b + (a&b)<<1

3、进位和非进位的和之间不能用加法直接相加,这里百分百就要用到递归呀,而递归的终止条件就是进位为0,返回非进位和。 为啥是这样?你举个最简单的例子就行了,比如 2+3 ,进位是不是0,整个和是不是非进位和?

class Solution {
    
    public int add(int a, int b) {// 假如 b是进位  a是非进位和
        if(b==0){
            return a; 
        }

        int c = (a&b)<<1; // 进位赋值给c,准备下一次递归使用
        int d = a^b; // 非进位和赋值给d ,准备下一次递归使用
        return add(d,c);

    }
}

方法二:

喵~ (编辑过)2020-11-18

完全一位一位的模拟二进制加法,仅仅是不用+号处理32次循环,就难了我半天,我太菜了

class Solution {
    public int add(int a, int b) {
        int ans = 0, mark = 0;
        int count = 0xffffffff;
        while ((count&1) == 1) {
            ans |= ((a & 1) ^ (b & 1) ^ mark) << 32 - Integer.bitCount(count);
            mark = (a & b & 1) | (a & 1 & mark) | (b & 1 & mark);
            a >>=1;
            b >>=1;
            count >>>= 1;
        }
        return ans;
    }
}

方法三:

K神 解题思路:

本题考察对位运算的灵活使用,即使用位运算实现加法。

设两数字的二进制形式 a, b ,其求和 s = a + b ,a(i)代表 a 的二进制第 i 位,则分为以下四种情况:

作者:jyd
链接:https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/
来源:力扣(LeetCode)

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

kckevin 2020-05-05

大佬思路非常清晰,把a+b转换成非进位和+进位,由于不能用加法,因此要一直转换直到第二个加数变成0。 用递归的写法比循环更容易一下子看懂

class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        // 转换成非进位和 + 进位
        return add(a ^ b, (a & b) << 1);
    }
}

总结

以上就是本题的内容和学习过程了,和上一题都是位运算的题,得记,用的多了就好了。

欢迎讨论,共同进步。

原文链接:https://blog.csdn.net/qq_39295220/article/details/117336468



所属网站分类: 技术文章 > 博客

作者:听说你很拽

链接:http://www.javaheidong.com/blog/article/207148/54546f3e81f68fe73173/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

19 0
收藏该文
已收藏

评论内容:(最多支持255个字符)