网站建设资讯

NEWS

网站建设资讯

LeetCode中如何不用加减乘除做加法

这篇文章给大家分享的是有关LeetCode中如何不用加减乘除做加法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

成都创新互联公司是一家专业提供洪江企业网站建设,专注与成都网站设计、做网站、成都h5网站建设、小程序制作等业务。10年已为洪江众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。

题目描述

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

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

题目样例

                 

示例

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

题目思考

  1. 不能用四则运算, 那还能用哪些运算符来实现呢?
                 

解决方案

                 
思路
  • 相比昨天的题目                     剑指 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
class Solution:
    def add(self, a: int, b: int) -> int:
        # 32位数掩码
        mask = 0XFFFFFFFF
        # 32位数的最大正数
        posMx = 0X7FFFFFFF
        while b != 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
        return a if a <= posMx else ~(a ^ mask)
                                   
Java
class Solution {
    public int add(int a, int b) {
        while (b != 0)
        {
            int smwithoutcarry = a ^ b;
            int carry = (a & b) << 1;
            a = smwithoutcarry;
            b = carry;
        }
        return a;
    }
}

感谢各位的阅读!关于“LeetCode中如何不用加减乘除做加法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!


标题名称:LeetCode中如何不用加减乘除做加法
转载来于:http://cdweb.net/article/ppccso.html