leetcode17 Sum of Two Integers

╰+攻爆jí腚メ 2021-12-14 04:51 172阅读 0赞

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
    
    Example 1:
    
    Input: a = 1, b = 2
    Output: 3
    Example 2:
    
    Input: a = -2, b = 3
    Output: 1

指定两个整数，对齐求和，但是不可以使用加号或者减号。

这个题16年校招的时候遇到过，所以有点印象，解法就是按照位运算来求解，我们可以看一下位运算，分析一下：  
1.将两个整数以二进制表示，两个数的加法，即对应位上的数加法，如果两个数的某一位不同（一个为0，一个为1），则相加后该位为1；如果相同，分两种情况，同为0，则相加后还是0，如果同为1，相加后结果仍为0，但需要向更高位进位；  
2.对位进行相加时，如果两个位相同，结果为0，不同，结果为1，这即位的异或运算；进位仅发生在两个位同为1的情况下，即位的与运算，与运算的结果，位为1的表示该位上发生了进位，进位实质上就是在更高位上加1，即左移一位，于是，最终的结果为异或的结果与进位的结果之和，问题又回到了求两个数之和，重复上述操作，直到进位为0为止；复杂度为O(n)

class Solution {
        public int getSum(int a, int b) {
            int bitXor = 0;
        int bitAnd = 0;
        while (0 != b) {
            bitXor = a ^ b;  // 异或，提取出不同位
            bitAnd = a & b;  // 与，提取进位
            a = bitXor;
            b = bitAnd << 1;
        }
        return a;
        }
    }

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Two Integers.
    Memory Usage: 31.6 MB, less than 100.00% of Java online submissions for Sum of Two Integers.

下面是discuss中的解法，有的类似有的利用了递归形式。

code1和我的思路基本相同，  
首先对a和b进行按位与，求一个结果carry，  
然后对a和b进行按位异或，求一个结果并赋值给a,  
最后最b赋值把carry的值左移一位。  
一直循环，知道b为0或者这里不存在carry

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

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Two Integers.
    Memory Usage: 31.8 MB, less than 100.00% of Java online submissions for Sum of Two Integers.

下面是递归形式:

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

Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Two Integers.
    Memory Usage: 31.7 MB, less than 100.00% of Java online submissions for Sum of Two Integers.

拓展：ab的减法：

public static int getSubtract(int a, int b) {
                while (b != 0) {
                    int borrow = (~a) & b;
                    a = a ^ b;
                    b = borrow << 1;
                }
    
                return a;
            }

递归形式：

public static int getSubtract(int a, int b) {
        return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
    }

参考文章：  
https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

https://en.wikipedia.org/wiki/Two%27s\_complement

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20211213/bb9e2b68a0d64ef285b517f8fa4505f7.png