Skip to content

Latest commit

 

History

History
78 lines (51 loc) · 4.15 KB

File metadata and controls

78 lines (51 loc) · 4.15 KB

不用加减乘除做加法

描述

来源:https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215

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

思考

对于数字运算,如果说四则运算不能用的话,那么我们只能用位运算来做了。

我们以 5 + 17 为例 结果为 22,那么 22 的计算结果,我们可以分为三步 来进行:

​ 第一步: 只做各位相加不进位 也就是说 没一位上的数字 相应的来相加 但是不进位,那么 5 + 7 为 12

​ 个位数 5 和 7 相加 不进位 是2 十位是0 和1 相加 为 1

​ 第二步: 5 + 7 中有进位,进位值 是10 ;

​ 第三步: 把前面两个结果 加起来: 12 + 10 = 22

以上为我们用十进制计算的 策略,那么 我们用于位运算中是不是也合适,我们来举个栗子:

还是以 5 + 17 为例,那么 5 的二进制是101 ; 17 的二进制是 10001;

第一步:各位相加 但不进位: 101 + 10001 = 10110 不进位的话 结果为 10100 (最后一位两个数都是1,相加的结果需要进位,但是这一位不进位,意味着结果仍然是0)

第二步: 记下进位,它只在最后一位相加时产生了一个进位。

第三步: 把前面两个结果相加,得到的结果是 10110.

那么现在我们把前面的 二进制的加法用位运算来替代的话

第一步的 求 和 运算就是 不考虑 进位的话,对每一位来相加,0 和0 以及 1 和1 的结果都是0 , 0+1 或者 1+0 的结果 都是1;那么我们会看出它与我们学过的异或运算相同,就是相同为假,不同为真,所以叫 异 或 XOR 。

第二步: 对0 加 0、1加0、0加1 而言,都不会产生进位,只有1+1 的时候,会产生一个进位。此时 我们可以想象成两个数 先做了一个 位 与 & 运算,然后再向 左移 一位。只有两个数是1 的时候,位与 & 得到的结果是 1,其余的都是0。

第三步:把前面两个步骤的结果再相加,然后在继续判断是否有进位,直到没有进位为止,那么此时的相加的过程,依然是重复前面的两步,直到不产生进位为止。

不用加减法算和运算

代码

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        #第一种代码:循环。简洁但是原理相同,那么我们以下面第二段代码为例;来解析。
        # while (num2):
        #     num1, num2 = (num1 ^ num2) & 0xFFFFFFFF, ((num1 & num2) << 1) & 0xFFFFFFFF
        # return num1 if num1 <= 0x7FFFFFFF else ~(num1 ^ 0xFFFFFFFF)
		
        #第二种代码:
        #首先两个数做 一个 异或 运算^ 那就是 在不进位的情况下,让两个相加 求和。
        xorNum = num1 ^ num2
        #让两个数 做 位与 操作,然后再向 左 移 一位,得到它 向前进位的值。
        andNum = (num1 & num2) << 1
		#判断,当 进位 的值不等于0 的时候,说明 一直有进位,也就是 过程没有结束。
        while andNum != 0:
            #那么我们就继续上面的操作。但是这次的 数值 改为上次的两个结果,
            #一个 是异或的结果,一个是 与 操作 & 以后 左移一位的 结果。
            tmp1 = xorNum ^ andNum
            tmp2 = (xorNum & andNum) << 1
			#因为如果这个数为负数的话,那么负数 左移 一位与正数 不同,负数 是数值变小,正数 数值变大
            #如果是正数的话那么这一步就 不变,如果是负数的话,这一步就对负数来起作用。
            #对于python来说  负数的 二进制 可能会有无数个1,我们用这个方法让它变成一个可数的数字长度。
            tmp1 = tmp1 & 0xffffffff

            xorNum = tmp1
            andNum = tmp2
         #一个负整数(或原码)与其补数(或补码)相加,和为模。 0xffffffff 
		# ~(xorNum ^ 0xFFFFFFFF)  这个是 异或数  与  模 来 异或,最后 按位 取反 来求得 负数的补码。
        return xorNum if xorNum <= 0x7ffffff else ~(xorNum ^ 0xFFFFFFFF)