题目描述

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

# -*- coding: utf-8 -*-
# @Time         : 2019-10-17 20:50
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : addWithoutElementaryArithmetic.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


class Solution:
    """
    ~n = -(n + 1)
    其实这种trick，感觉如果之前没有见过是很难想出来的。
    这种题目，只要是涉及到不允许用四则运算的，大概率都会跟位运算、逻辑运算、递归挂钩。

    假设需要计算5 + 7 = 12
    0101
   +0111
   =1100

    拆解一下：
    第1步： 0101 + 0111 = 0010 (不考虑进位相加)
    第2步：进位出现的位置是两个数在该位置都为1的情况，例如这里就是在第0、2位 (从右往左记录索引)
          即，进位情况为 0101，但既然涉及到了进位，是需要左移1位的(不然就是没有进位，有进位必然
          是只左移1位)，因此进位结果为0101 << 1 --> 1010
    第3步：将第1步、第2步的结果相加，即 0010 + 1010 = 1100.

    而第3步的结果是可以通过重复第1、2步来得到的，也就是说，
    我们可以将原本的0101 + 0111 --> 0010 + 1010
    而后者可以继续利用第1、2步的算法展开，得到：1000 + 0100
    再展开，得到：1100 + 0000，注意到此时的1100就是我们需要的结果。

    总结上述的计算过程，我们先计算不带进位的和，然后计算进位是多少，重复上述步骤直到进位为0即可。
    具体来说，计算不带进位的和只需要进行异或运算即可；计算进位只需要计算位与运算后左移1位即可。
    """
    def Add(self, num1, num2):
        while num2:
            print(num1, num2)
            # 不带进位的和的计算：异或。
            # 注意到由于Python的数字是不限位数的，而我们用的这种算法是针对有限位数的，
            # 因此需要添加一个界限，这里以32位为界
            sum_without_carry = (num1 ^ num2) & 0xFFFFFFFF
            carry = ((num1 & num2) << 1) & 0xFFFFFFFF
            num1, num2 = sum_without_carry, carry

        # 如果最后的和是正数或0，直接输出即可
        # 如果是负数，需要将其正确输出。
        # 由于我们已经有一个32位的num1，但是python不能识别最高位为符号位，
        # 因此首先我们可以先按位取反(这里用到的是和全1做异或)，然后对结果取反。

        # 注意这里的num1 ^ 0xFFFFFFFF = ~num1 & 0xFFFFFFFF
        # 区别在于Python中的每一次异或运算都会将位数扩展成无限，因此需要对其重新设定界限

        # 而因为我们获取到的数的位表示都是补码形式，而我们实际需要的是原码形式，
        # 对于正数来说，正数的原码补码都一样；
        # 对于负数来说，负数的补码等于原码取反(反码) + 1.

        # 我们这里的异或操作相当于取得了反码，还需要+1，
        # 并将负号加进去(因为我们在取反的时候将负号为也置为0了)
        # 而我们这里利用到一个取反的特性： ~n = -(n + 1)。
        # 因此，我们对按位取反后的结果再进行一次取反就可以

        # 以下三种方法都是可以的
        # ~(num1 ^ 0xFFFFFFFF)：先异或再取反
        # -((~(num1 & 0xFFFFFFFF) & 0xFFFFFFFF) + 1)：先取反再+1，最后将负号不上
        # ~(~(num1 & 0xFFFFFFFF) & 0xFFFFFFFF)：应用了对x取反再取反得到x的原理，只是中间加了位数界限

        return num1 if num1 <= 0x7FFFFFFF else ~(num1 ^ 0xFFFFFFFF)
        # return num1 if num1 <= 0x7FFFFFFF else ~(~(num1 & 0xFFFFFFFF) & 0xFFFFFFFF)
        # return num1 if num1 <= 0x7FFFFFFF else -((~(num1 & 0xFFFFFFFF) & 0xFFFFFFFF) + 1)

    def Add2(self, num1, num2):
        while num2 != 0:
            print(num1, num2)
            sum_without_carry = num1 ^ num2
            carry = (num1 & num2) << 1
            num1, num2 = sum_without_carry, carry
        return num1


def main():
    solution = Solution()
    print(solution.Add2(-5, 7))
    # print(solution.Add(-5, 7))


if __name__ == '__main__':
    main()