1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录

[剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录

第 65 题:不用加减乘除做加法

传送门: 不用加减乘除做加法牛客网 online judge 地址

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

样例:

输入:num1 = 1 , num2 = 2

输出:3

思路:不用加减乘除,那就只能用位运算了。

liwei20191011111_1.png

下面是交换两个数的特殊写法,了解一下。

liwei201910117_2.png

Python 代码:在 Python 内部对整数的处理分为普通整数和长整数,普通整数长度为机器位长,通常都是 32 位,超过这个范围的整数就自动当长整数处理,而长整数的范围几乎完全没限制。

Python 代码:

  class Solution(object):
        def add(self, num1, num2):
            """
            :type num1: int
            :type num2: int
            :rtype: int
            """
            while num2 != 0:
                # 不进位加法
                temp = num1 ^ num2
                # 加法进位
                num2 = (num1 & num2) << 1
                # 把高于 32 位的 1 全部变成 0
                num1 = temp & 0xFFFFFFFF
            return num1 if num1 >> 31 == 0 else num1 - (1 << 32)

说明:Python 中 int 类型的最大值是 0x7fffffff

Python 代码:与上面的写法等价

  class Solution(object):
        def add(self, num1, num2):
            """
            :type num1: int
            :type num2: int
            :rtype: int
            """

            while True:
                # 不进位加法
                s = num1 ^ num2
                # 计算进位
                carry = num1 & num2

                # 手动把高于 32 位的部分变成 0
                num1 = s & 0xFFFFFFFF
                num2 = carry << 1

                if carry == 0:
                    break
            # 如果是正数和 0 ,就直接返回这个正数好了
            if num1 >> 31 == 0:
                return num1
            # 如果是负数
            return num1 - (1 << 32)

Java 代码:

  public class Solution {

        public int Add(int num1, int num2) {
            int sum = 0;
            while (true) {
                // 计算个位
                sum = num1 ^ num2;

                int carry = num1 & num2;
                if (carry == 0) {
                    break;
                }
                num1 = sum;
                // 计算进位
                num2 = carry << 1;

            }
            return sum;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int add = solution.Add(14, 15);
            System.out.println(add);
        }
    }

还可以用“全加器”实现。

liwei201910111_3.png

Python 代码:

  class Solution(object):
        def add(self, num1, num2):
            """
            :type num1: int
            :type num2: int
            :rtype: int
            """
            # 特判
            if num1 == 0 or num2 == 0:
                return max(num1, num2)

            res = 0
            # 进位
            carry = 0
            for i in range(32):
                a = num1 & (1 << i)
                b = num2 & (1 << i)
                # 不进位的和
                s_ = (a ^ b) ^ carry
                # 下面计算进位,三者之中,任意两者同为 1 的时候,就可以进位
                carry = (a & b) | (a & carry) | (b & carry)
                carry <<= 1
                res += s_
            if res >> 31 == 0:
                return res
            return res - (1 << 32)

Java 代码:

  public class Solution {

        public int Add(int num1, int num2) {
            int sum = 0;
            while (true) {
                sum = num1 ^ num2;
                int carry = num1 & num2;
                if (carry == 0) {
                    break;
                }
                num1 = sum;
                num2 = carry << 1;

            }
            return sum;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            int add = solution.Add(14, 15);
            System.out.println(add);
        }
    }

Java 代码:

  public class Solution2 {

        // 书上的写法
        public int Add(int num1, int num2) {
            int sum = 0;
            int carry = 0;
            do {
                sum = num1 ^ num2;
                carry = num1 & num2;

                num1 = sum;
                num2 = carry << 1;
            } while (carry != 0);
            return sum;
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 65 题] “不用加减乘除做加法”做题记录

链接:https://www.javajike.com/article/3304.html

« [剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录
[剑指 Offer 第 2 版第 66 题] “构建乘积数组”做题记录»

相关推荐

QR code