SumOfTwoIntegers [source code]

public class SumOfTwoIntegers {
    public int getSum(int a, int b) {
        boolean carry = false;
        Deque<Boolean> deque = new ArrayDeque<>();
        while (deque.size() <= 32) {      
            if (a == 0 && b == 0 && !carry) break;
            boolean a_bit = (a & 1) == 1 ? true : false;        
            boolean b_bit = (b & 1) == 1 ? true : false;
            boolean res_bit = false;
            if (!a_bit && !b_bit && !carry) {
                carry = false;
                res_bit = false;
            } else if ((!a_bit && !b_bit && carry) || (!a_bit && b_bit && !carry) || (a_bit && !b_bit && !carry)) {
                carry = false;
                res_bit = true;
            } else if ((!a_bit && b_bit && carry) || (a_bit && !b_bit && carry) || (a_bit && b_bit && !carry)) {
                carry = true;
                res_bit = false;
            } else if (a_bit && b_bit && carry) {
                carry = true;
                res_bit = true;
            }
            deque.push(res_bit);
            a = a >> 1;     
            b = b >> 1;
        }
        int res = 0;
        for (Boolean bit : deque) {
            System.out.print(" " + bit);
            res = (res << 1) | (bit ? 1 : 0);
        }
        return res; 
    }

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

算法的速度是4ms, 属于非常慢的了. 而且我也花了很大的功夫才写出来, 结果 lc 上面的成功率这么高, 我也是搞不懂了, 也许这个就是体现出了基础的差距; 尽管如此, 这个题目还是学到了大量的知识;
另外这些 bit 题目做多了, 我也是越来越感觉有必要把hacker's delight看一看, 感觉我对于这些 bit 题基本是完全没有头绪;

刚开始的想法是用一个函数把 int 转换成boolean[], 但是后来发现这个做法是不行的, 用了-; 然后想到如果不准用加减号, 那么连基本的 forloop 都不好写了; 所以这个题目的所有类似loop 里面var update的操作, 基本只能依靠直接的bit operation来完成, 尤其是 shift;

一开始有一个想法, 就是用 recursion 写. 用 recursion 写当然有不好的地方, 因为要不停的传值, 这个是有 cost 的, 但是recursion 的好处是base case很好定义;
后来突然想到就算是用一个简单的 loop 来写, base 其实也不难写: premature exit就行了; 说到底, base 其实就是termination 的意思, 这个无论是 recursive 还是 iterative 都是可以做到的;
//我当时的想法是如果a, b, carry当中至少有两个是0, 那么可以直接return 不是0的那一个, 后来想想这个思路其实不对;

carry 只需要一位, 而不是整个 array, 这个应该不用多讲了;

条件判断的话, 因为这里是三个 bit, 所以直接枚举就行了, 搞太复杂也没有意思(而且这种明显让你实现底层的算法, 也不用太担心代码显得不好看). 具体的表达用类似 CNF 的方式写就行了; 不对, 好像是 DNF?

res = (res << 1) | (bit ? 1 : 0);

这个是在最后求和的时候用到的一个表达方式, 能够想到这个还是挺不简单的(因为常规做法是*2, 再+1, 这样不停递归, 但是这里不能用加法);

需要注意的是这里不能直接用(res << 1) | bit, 因为6 | true这样的表达在 JAVA 里面是不合法的; 这个时候就想到C++的好了;

boolean a_bit = (a & 1) == 1 ? true : false;

这里值得注意的是这个括号: bit 运算的优先级非常的低, 以后碰到基本最好都给一个括号;

这里的 Deque 一开始的用的是 Stack. 但是 Stack 的 iterator 的顺序其实不是 LIFO, 一般更好的做法是用deque;

deque.size() <= 32

一开始 while 的 header 里面是没有 condition 的, 但是后来加了这个长度限制, 因为实际的 int 的表达方式是2's complement, 如果涉及到负数的时候, 比如-1的时候, 你是永远不可能碰到你这里定义的 ab 的 prefix 和carry 一起全都是0的情况的;

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