文档章节

不使用+-实现加法 Sum of Two Integers

叶枫啦啦
 叶枫啦啦
发布于 2017/08/22 15:38
字数 614
阅读 5
收藏 0

问题:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

解决:

【分析】

首先我们可以分析如何做十进制的加法
比如是如何得出5+17=22这个结果的。实际上,我们可以分成三步的:
① 只做各位相加不进位,此时相加的结果是12(个位数5和7相加不要进位是2,十位数0和1相加结果是1);
② 做进位,5+7中有进位,进位的值是10;
③ 把前面两个结果加起来,12+10的结果是22,刚好5+17=22。

对于二进制进行分析:

5的二进制是101,17的二进制10001。
还是试着把计算分成三步:
① 各位相加但不计进位,得到的结果是10100(最后一位两个数都是1,相加的结果是二进制的10。这一步不计进位,因此结果仍然是0);
② 记下进位。在这个例子中只在最后一位相加时产生一个进位,结果是二进制的10;
③ 把前两步的结果相加,得到的结果是10110,正好是22。
由此可见三步走的策略对二进制也是管用的。

接下来我们试着把二进制上的加法用位运算来替代。

不考虑进位,对每一位相加。0 + 0 = 0、1 + 1 = 0;1 + 0 = 1、0 + 1 = 1;这种效果与异或是相同的。对于异或而言,两个操作数的位中,相同则结果为0,不同则结果为1。
记录进位,0 + 0,1 + 0,0 + 1都不会产生进位,1 + 1会产生进位。所以可以理解为两个数先做位与运算,然后再向左移动一位。只有两个数都是1的时候,位与得到的结果是1,其余都是0。
把前两个步骤的结果相加。如果我们定义一个函数,③就相当于输入前两步骤的结果来递归调用自己。

代码:

class Solution { //0ms
    public int getSum(int a, int b) {
        if(b == 0) return a;
        if(a == 0) return b;
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return getSum(sum,carry);
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
LeetCode:Sum of Two Integers - 不使用加减法运算符的整数加法

1、题目名称 Sum of Two Integers(不使用加减法运算符的整数加法) 2、题目地址 https://leetcode.com/problems/sum-of-two-integers/ 3、题目内容 英文: Calculate the sum of two integ...

北风其凉
2016/07/19
580
0
A+B Problem II 大数加法

A+B Problem II http://acm.nyist.net/JudgeOnline/problem.php?pid=103 时间限制:3000 ms | 内存限制:65535 KB 难度:3 输入 The first line of the input contains an integer T(1<=T<=......

阿豪boy
2017/02/10
16
0
计算子序列和是定值的子序列个数

题目如下: Counting Subsequences Time Limit: 5000 MSMemory Limit: 65536 K Description "47 is the quintessential random number," states the 47 society. And there might be a grain......

BladeStorm
2014/07/16
737
0
Codeforces C. Split a Number(贪心大数运算)

题目描述: time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output Dima worked all day and wrote down on a long paper strip......

小张人
07/27
0
0
LeetCode算法题-Sum of Two Integers(Java实现)

这是悦乐书的第210次更新,第222篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第78题(顺位题号是371)。计算两个整数a和b的总和,但不允许使用运算符+和 - 。例如: 输入:...

小川94
2018/12/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud 笔记之Spring cloud config client

观察者模式它的数据的变化是被动的。 观察者模式在java中的实现: package com.hxq.springcloud.springcloudconfigclient;import org.springframework.context.ApplicationListener;i...

xiaoxiao_go
8分钟前
2
0
CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
今天
3
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
7
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
7
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部