leetcode371. 两整数之和

题目说不能使用运算符 + 和 -,那么我们就要使用其他方式来替代这两个运算符的功能。
位运算中的加法
我们先来观察下位运算中的两数加法,其实来来回回就只有下面这四种:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0(进位 1)

仔细一看,这可不就是相同位为 0,不同位为 1 的异或运算结果嘛~

异或和与运算操作
我们知道,在位运算操作中,异或的一个重要特性是无进位加法。我们来看一个例子:

a = 5 = 0101
b = 4 = 0100

a ^ b 如下:

0 1 0 1
0 1 0 0
-------
0 0 0 1

a ^ b 得到了一个无进位加法结果,如果要得到 a + b 的最终值,我们还要找到进位的数,把这二者相加。在位运算中,我们可以使用与操作获得进位:

a = 5 = 0101
b = 4 = 0100

a & b 如下:

0 1 0 1
0 1 0 0
-------
0 1 0 0

由计算结果可见,0100 并不是我们想要的进位,1 + 1 所获得的进位应该要放置在它的更高位,即左侧位上,因此我们还要把 0100 左移一位,才是我们所要的进位结果。

那么问题就容易了,总结一下:

a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
无进位加法使用异或运算计算得出
进位结果使用与运算和移位运算计算得出
循环此过程,直到进位为 0
在 Python 中的特殊处理
在 Python 中,整数不是 32 位的,也就是说你一直循环左移并不会存在溢出的现象,这就需要我们手动对 Python 中的整数进行处理,手动模拟 32 位 INT 整型。

具体做法是将整数对 0x100000000 取模,保证该数从 32 位开始到最高位都是 0。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1 关键字 1.1 关键字的概述 Java的关键字对java的编译器有特殊的意义,他们用来表示一种数据类型,或...
    哈哈哎呦喂阅读 672评论 0 0
  • 我们知道,计算机最基本的操作单元是字节(byte),一个字节由8个位(bit)组成,一个位只能存储一个0或1,其实...
    JxYoung阅读 42,023评论 22 90
  • 运算符是处理数据的基本方法,用来从现有的值得到新的值。JavaScript 提供了多种运算符,本章逐一介绍这些运算...
    徵羽kid阅读 699评论 0 0
  • 关于二进制数 求二进制数1的个数:知识点:在计算机中所有数据都是二进制类型的,所以不用特意的去转换。n & (n ...
    我不饿我不想吃东西阅读 606评论 0 0
  • 一、resources 生成7个地址对应于7个controller#action,其中controller#upd...
    wayoona阅读 206评论 0 0