Eric's Blogs

Better Code, Better Life

0%

不用加减乘除做加法

发表于 分类于
本文字数： 955 阅读时长 ≈ 1 分钟

题目描述

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

解答

1
2
3
4
5
6
7
8
public int Add(int num1, int num2) {
    while (num2 != 0) {//当进位为零时停止
        int c = (num1 & num2) << 1;//进位需要左移一次
        num1 = num1 ^ num2;
        num2 = c;
    }
    return num1;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215?answerType=1&f=discussion
来源：牛客网

方法：位运算

知识补充：

  1. 按位与&，按位或|， 按位异或^
    图片说明
  2. 补码
    计算机中存整数n是用补码存的。
  • 如果n为正数，则原码=反码=补码
  • 如果n为负数，则补码=反码+1

本题是考察对位运算的运用，使用位运算来实现两数的加法。
设两数字的二进制形式 a，b ，其求和 s = a + b ，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：
图片说明

观察发现，无进位和运算就是按位异或结果，进位就是与运算结果但是需要左移一位，因为进位影响下一位的运算。
所以s = a + b,其实就是无进位和+进位的结果。
算法步骤：

  1. 计算a和b的无进位和，和进位
  2. 如果进位不为0，则说明a+b的结果等于无进位和+进位，此时，把无进位和作为a，进位作为b，继续计算
  3. 如果进位等于0， 说明此时a+b的结果就等于无进位和，返回无进位和即可。
    如图：
    图片说明

Q：你可能有疑问，如果是一个数为负数或者两个数都为负数怎么办？
A：上述补码的介绍，补码就是解决减法的问题，计算机把减法看做加法来运算。
所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int Add(int num1, int num2)
    {
        while (num2 != 0) {
            // 负数左移会在低位补1，所以转化为无符号整数
            int c = ((unsigned int)(num1 & num2)) << 1; 
            num1 ^= num2;
            num2 = c;
        }
        return num1;
    }
};

时间复杂度：O(1)
空间复杂度：O(1)