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

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

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

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

样例：

输入：num1 = 1 , num2 = 2

输出：3

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

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

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);
        }
    }

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

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/