养生网站源码下载,wordpress 父分类,宝山网站建设宝山,企业网站建设心得❓ 剑指 Offer 65. 不用加减乘除做加法
难度#xff1a;简单
写一个函数#xff0c;求两个整数之和#xff0c;要求在函数体内不得使用 “”、“-”、“*”、“/” 四则运算符号。
示例: 输入: a 1, b 1 输出: 2 提示#xff1a;
a, b 均可能是负数或 0结果不会溢出 …❓ 剑指 Offer 65. 不用加减乘除做加法
难度简单
写一个函数求两个整数之和要求在函数体内不得使用 “”、“-”、“*”、“/” 四则运算符号。
示例: 输入: a 1, b 1 输出: 2 提示
a, b 均可能是负数或 0结果不会溢出 32 位整数
思路位运算
预备知识 —— 一篇文章搞懂位运算!!!
有符号整数通常用补码来表示和存储补码具有如下特征
正整数的补码与原码相同负整数的补码为其原码除符号位外的所有位取反后加 1。可以将减法运算转化为补码的加法运算来实现。符号位 与 数值位 可以一起参与运算。
a ^ b 表示没有考虑进位的情况下两数的和(a b) 1 就是进位。
递归会终止的原因是 (a b) 1 最右边会多一个 0那么继续递归进位最右边的 0 会慢慢增多最后进位会变为 0递归终止。 递归可以转换为迭代从而减少空间复杂度 代码(C、Java)
法一递归 C
class Solution {
public:int add(int a, int b) {return b 0 ? a : add(a ^ b, (a b) 1);}
};Java
class Solution {public int add(int a, int b) {return b 0 ? a : add(a ^ b, (a b) 1);}
}法二迭代 C
class Solution {
public:int add(int a, int b) {while(b ! 0){int tmp a ^ b;b (a b) 1;a tmp;}return a;}
};Java
class Solution {public int add(int a, int b) {while(b ! 0){int tmp a ^ b;b (a b) 1;a tmp;}return a;}
}运行结果 复杂度分析
时间复杂度 O ( l o g ( m a x i n t ) ) O(log(max_int)) O(log(maxint))其中我们将执行位运算视作原子操作。。空间复杂度 O ( 1 ) O(1) O(1)迭代。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
