SumOfTwoIntegersOPT [source code]

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

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

    public static void main(String[] args) {
        SumOfTwoIntegersOPT tester = new SumOfTwoIntegersOPT();
        assert tester.getSum(20, 30) == 50 : "fail 20 + 30";
        assert tester.getSum(-1, 1) == 0 : "fail -1 + 1";
        System.out.println(tester.getSubtract(-7, 3));
    }
}

这个是 submission 最优解, 0ms;

从这个代码第一眼看去, 我那个按照 bit 一个一个做的方法貌似是太低级了;

这个是 lc 上面的解答:

I have been confused about bit manipulation for a very long time. So I decide to
do a summary about it here.

"&" AND operation, for example, 2 (0010) & 7 (0111) => 2 (0010)

"^" XOR operation, for example, 2 (0010) ^ 7 (0111) => 5 (0101)

"~" NOT operation, for example, ~2(0010) => -3 (1101) what??? Don't get frustrated here. It's called two's complement.

1111 is -1, in two's complement

1110 is -2, which is ~2 + 1, ~0010 => 1101, 1101 + 1 = 1110 => 2

1101 is -3, which is ~3 + 1

虽然 ~3 = -3 -1这个看上去更好记忆, 但是这个式子实际上没有什么实际的意义: ~本身只是一个操作; 而-3 = ~3 + 1则是给出了一个 negate 的计算方法;

so if you want to get a negative number, you can simply do ~x + 1

Reference:

https://en.wikipedia.org/wiki/Two%27s_complement

https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

For this, problem, for example, we have a = 1, b = 3,

In bit representation, a = 0001, b = 0011,

First, we can use "and"("&") operation between a and b to find a carry.

carry = a & b, then carry = 0001

Second, we can use "xor" ("^") operation between a and b to find the different bit, and assign it to a,

Then, we shift carry one position left and assign it to b, b = 0010.

Iterate until there is no carry (or b == 0)

// Iterative  
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;  
}  

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

    return a;  
}  

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

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

// Get negative number  
public int negate(int x) {  
    return ~x + 1;  
}

仔细理解了这个算法的话, 其实是非常聪明的一个算法;

另外一个可能不好理解的东西就是这里减法的实现:

        while (b != 0) {  
            int borrow = (~a) & b;  
            a = a ^ b;  
            b = borrow << 1;  
        }

其实你就想, 什么时候应该是有 borrow? 应该是a == 0 && b == 1的时候;
所以这里的 borrow 的计算其实很顺理成章; 然后下一步的 xor 其实也不难理解, 因为二进制的加法和减法本来就可以统一用 xor 来表示的;
那么为什么要把 borrow 左 shift 呢? 其实就跟 carry 需要左 shift 是一样的原理, 向高位移动; 你可能会怀疑到底"减法"本身体现在哪里? 因为用的是two's complement, 所以加法跟减法其实就是一回事了;

另外前面一个没有考虑的问题:
为什么termination condition是b != 0? 因为如果没有 carry 产生, 说明 xor 完成得到的结果就是真实的加法(也是减法)结果, 没有进位, 这个计算就算结束了;

Problem Description

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.

Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:51.23%
Contributor: LeetCode
Topics:
Bit Manipulation
You might like:
(M) Add Two Numbers
Company:
Hulu