[每日一题] 第六题:不用加减乘除做加法

题目描述

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

示例:

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

提示:

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

题解

方法一:位运算

解题思路

本题考查对位运算的灵活使用,即使用位运算实现加法。

设两数字的二进制形式 a,b,其求和 s = a + b,a(i) 代表 a 的二进制第 i 位,则分为以下四种情况:

a(i) b(i) 无进位和 n(i) 进位 c(i+1)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

观察发现,无进位和异或运算 规律相同,进位与运算 规律相同(并需左移一位)。因此,无进位和 n 与进位 c 的计算公式如下:

n = a ⊕ b 非进位和:异或运算
c = a & b << 1 进位:与运算 + 左移一位

(和 s)= (非进位和 n) + (进位 c)。即可将 s = a + b 转化为:s = a + b => s = n + c

循环求 n 和 c,直至进位 c = 0;此时 s = n,返回 n 即可。

[每日一题] 第六题:不用加减乘除做加法

Q : 若数字 aa 和 bb 中有负数,则变成了减法,如何处理?

A : 在计算机系统中,数值一律用 补码 来表示和存储。补码的优势: 加法、减法可以统一处理(CPU只有加法器)。因此,以上方法 同时适用于正数和负数的加法 。

代码

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

复杂度分析

时间复杂度O(1) :最差情况下(例如 a = 0x7fffffff,b = 1 时),需循环 32 次,使用 O(1) 时间;每轮中的常数次位操作使用 O(1) 时间。

空间复杂度O(1) :使用常数大小的额外空间。

个人理解

以 9 + 7 为例,详细手动模拟一下步骤:

十进制模拟

第一次循环,计算 9 + 7:

无进位和:9 + 7 = 6。

进位:个位进一位为 1,进到十位了,所以要 * 10,即 10。

第二次循环,计算 6 + 10:

无进位和

个位:0 + 6 = 6

十位:1 + 0 = 1

结果为 16

进位:个位无进位,十位无进位,

所以最终结果为 16。

二进制模拟

9 的二进制为:1001

7 的二进制位:111

第一次循环,计算 1001 + 111:

无进位和(异或):1001 ^ 111 = 1110

进位(与):1001 & 111 = 1

十进制进位就应该 x10,二进制进位就得左移一位,所以 1 << 1 = 10

第二次循环,计算 1110 + 10:

无进位和(异或):1110 ^ 10 = 1100

进位(与):1110 & 10 << 1 = 10 < < 1 = 100

第三次循环,计算 1100 + 100:

无进位和(异或):1100 ^ 100 = 1000

进位(与):1100 & 100 << 1 = 100 < < 1 = 1000

第四次循环,计算 1000 + 1000:

无进位和(异或):1000 ^ 1000 = 0000

进位(与):1000 & 1000 << 1 = 1000 < < 1 = 10000

第五次循环,计算 0000 + 10000:

无进位和(异或):0000 ^ 10000 = 10000

进位(与):0000 & 10000 << 1 = 00000 < < 1 = 000000

这个时候就该结束了,因为此时无进位了。

此时 10000 的值就是最终结果,换成十进制为 16。

为什么十进制相加循环次数这么少?而二进制循环次数这么多呢? 因为二进制位数多,碰到特别情况,比如该情况,一位一位向上进,所以循环次数就多了。

那么什么时候结束循环呢? 就是没有进位的时候,不需要再加了。

为什么要有循环呢? 因为相加就会产生进位,进位了说明没算完,需要继续加上进位,知道没有进位。

题解来源

作者:jyd

链接:leetcode-cn.com/problems/bu-yong-j...

来源:力扣(LeetCode)

方法二:奇思妙想解法

代码

真没有运算符!!

class Solution:
    def add(self, a: int, b: int) -> int:
        result = [a,b]
        return sum(result)

题解来源

作者:luyao777

链接:leetcode-cn.com/problems/bu-yong-j...

来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)

链接:leetcode-cn.com/problems/bu-yong-j...

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!