leetcode Sum of Two Integers

leetcode Sum of Two Integers

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.

传送门：leetcode Sum of Two Integers

题意：给定两个数 a和b，求它们的和。要求不使用 +和-运算符

思路：

首先要知道，异或也被称为“模2和” ，so 这题就是运用异或的位运算啦。

我们可以每次取最低位来计算, 然后每次右移一位，注意点有：

进位为两个数字1
负数的情况下，右移最高位补的是1 ,因此值得注意要取到什么时候为止。 java有一个无符号右移>>>高位补0，因此结束条件可以为a!=0 b!=0（然而进位会被忽略）

C++

class Solution {
public:
	int getSum(int a, int b) {
		int ans = 0, carry = 0;
		for (int i = 0; i < 32; a >>= 1, b >>= 1, i++) {
			int lower_a = a & 1, lower_b = b & 1;
			ans |= (lower_a ^ lower_b ^ carry) << i;
			carry = (carry & lower_a) | (carry & lower_b) | (lower_a & lower_b);
		}
		return ans;
	}
};

Java

public class Solution {
    public int getSum(int a, int b) {
        int ans = 0, carry = 0;
        for (int i = 0; i < 32; a >>>= 1, b >>>= 1, i++) {
            int lower_a = a & 1, lower_b = b & 1;
            ans = (lower_a ^ lower_b ^ carry) << i;
            carry = (carry & lower_a)  (carry & lower_b)  (lower_a & lower_b);
        }
        return ans;
    }
}

第二种方法是直接进行异或操作。

a ^ b 直接算出a + b 每位上%2的结果，进位的话可以直接 (a & b)<<1得到（只有两个位均为1才会进位嘛，左移表示进到下一位啊）

C++

class Solution {
public:
	int getSum(int a, int b) {
		while (b != 0) {
			int c = a & b; //carry
			a ^= b; //add 
			b = c << 1;
		}
		return a;
	}
};

Java(和上面一样)

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
			int c = a & b; //carry
			a ^= b; //add 
			b = c << 1;
		}
		return a;
    }
}

也可以写成Oneline：

class Solution {
public:
	int getSum(int a, int b) {
		return b == 0 ? a : getSum(a^b, (a&b) << 1);
	}
};

PS:

Python 表示一个数不止32位。。

Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011". 来自 https://wiki.python.org/moin/BitwiseOperators

因此。。做这题要保证两个数在正确的范围内（本题是int，32bit）

如何做到呢？我们知道32bit 可以表示的无符号整数位0_{0xFFFFFFFF（全0}全1）

因此，我们使用&来保证该数是32bit.

int的0和正整数范围为0_{0x7FFFFFFF，int负数的范围为-0x80000000}-1,因此，大于0x7FFFFFFF的其实是最高位为1（这是符号位）。这样算出来是把最高位不当成符号位，我们还需要对负数的情况进行修正。

在具体实现上，我们可以先 &0x7FFFFFFF 然后取反，这样，-1变为-0x80000000(-2147483648) -2变为了-0x7FFFFFFF(-2147483647) ,因此，在^0x7FFFFFFF即可。。

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        MOD     = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF
        while b != 0:
            a, b = (a ^ b) & MOD, ((a & b) << 1) & MOD
        return a if a <= MAX_INT else ~(a & MAX_INT) ^ MAX_INT

也可以看https://discuss.leetcode.com/topic/49900/python-solution/2 上的思路

或者更巧妙的用(~0 << 31) a 即可，因为只需要把31位之后的全部置1, 感谢mach7提出

本题是leetcode 371 Sum of Two Integers 题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/