点击专辑上方“蓝字”关注我吧
题目难度: 简单
原题链接[1]
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号每日精选算法题, 大家记得关注哦~ 另外在公众号里回复offer就能看到剑指 offer 系列当前连载的所有文章了
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
a, b 均可能是负数或 0结果不会溢出 32 位整数
题目样例
示例
输入: a = 1, b = 1输出: 2题目思考
不能用四则运算, 那还能用哪些运算符来实现呢?解决方案
思路
相比昨天的题目剑指 Offer 64. 求 1+2+…+n - leetcode 剑指 offer 系列, 这道题目限制少了很多, 至少循环/条件判断/位运算这些都能用了我们先来尝试分析数字的二进制表示, 看看能否用位运算来替代加法如果某一位的两个数字都是 1, 那么这一位的加法就会产生进位, 所以与可以用来计算进位, 而且显然进位是要左移一位的接下来考虑如何得到当前位的加法结果.异或在两个数字都为 1 或者都为 0 的情况下结果是 0, 否则结果是 1, 换言之异或就是不带进位的加法将上面两步结合在一起, 我们就能把a+b转换成((a&b)<<1)+(a^b), 虽然这里仍然有加号, 但是我们将其置为新的 a 和 b, 循环这个过程, 直到进位变成 0, 这样最终异或结果就是两者之和了注意最终进位一定能变成 0, 这是因为如果有进位的话, 进位是会不断左移的, 而题目保证最终结果不会溢出, 那么经过若干次循环后, 一定会达到一个不需要进位的状态, 不然无限左移就会溢出了C++/JAVA 等语言分析到这里就 OK 了, 但 python 需要特别处理负数问题. 因为 python 的负数表示方法不是像其他语言那样的 32 位补码, 而是更高位也全是 1, 这样在处理负数的时候必须手动模拟 32 位补码, 才能正确得出结果, 不然最后结果就不满足 python 正确的负数表示方式, 而变成无符号正数了所以我们需要先将负数转成 32 位补码 (&0xFFFFFFFF, 正数仍为自身, 负数相当于 32 位补码形式, 因为去掉了更高位上的 1), 然后利用上述结果求完之后, 如果结果是负数(>0x7FFFFFFF)的话再转成正常的 python 负数表示方式(~(a ^ 0xFFFFFFFF), 即先对低 32 位的取反, 更高位不变, 然后整体再取反, 从而将大于等于 32 位的数字重新转成 1)下面代码额外列出了 Java 版本, 方便大家对比. Java 的负数就是 32 位补码表示, 所以不需要额外进行处理复杂度
时间复杂度 O(logN): 最多需要遍历所有位数, 数字 N 的位数为 logN空间复杂度 O(1): 只需要维护常数个变量代码
python 3
defadd(self,a:int,b:int)->int: #32位数掩码 mask=0XFFFFFFFF #32位数的最大正数 posMx=0X7FFFFFFF whileb!=0: #a是不带进位的和,都要转成32位整数 # b是进位, 都要转成32位整数 #循环直到进位为0,那么a就是最终结果 smwithoutcarry=(a^b)&mask carry=((a&b)<1)&mask a,b=smwithoutcarry,carry #最终如果是32位负数的话,需要将其转回python正常的负数表示形式(高于32位的全是1,而不是32位负数那样更高位全为0),做法是先对低32位的取反,更高位不变,然后整体再取反,从而将大于等于32位的数字重新转成1 returnaifa<=posMxelse~(a^mask)classSolution:
Java
publicintadd(inta,intb){ while(b!=0) { intsmwithoutcarry=a^b; intcarry=(a&b)<1; a=smwithoutcarry; b=carry; } returna; } }classSolution{
参考资料
[1]原题链接:https://leetcode-/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
你的每个赞和在看，我都喜欢！
