A plus B Problem

Question

• lintcode: (1) A + B Problem

  1. Write a function that add two numbers A and B.
     2. You should not use + or any arithmetic operators.
     3. 4. 5. Example
     4. Given a=1 and b=2 return 3
     5. 8. Note
     6. There is no need to read data from standard input stream.
     7. Both parameters are given in function aplusb,
     8. you job is to calculate the sum and return it.
     9. Challenge
     10. Of course you can just return a + b to get accepted.
     11. But Can you challenge not do it like that?
     12. Clarification
     13. Are a and b both 32-bit integers?
     14. Yes.
     15. Can I use bit operation?
     16. 20. Sure you can.

題解

不用加減法實現加法，類似數字電路中的全加器 (Full Adder)，XOR 求得部分和，OR 求得進位，最後將進位作爲加法器的輸入，典型的遞迴實現思路。

Java

  1. class Solution {
    2.     /*
    3.      * param a: The first integer
    4.      * param b: The second integer
    5.      * return: The sum of a and b
    6.      */
    7.     public int aplusb(int a, int b) {
    8.         int result = a ^ b;
    9.         int carry = a & b;
    10.         carry <<= 1;
    11.         if (carry != 0) {
    12.             result = aplusb(result, carry);
    13.         }
    14.   15.         return result;
    16.     }
    17. }

源碼分析

遞迴步爲進位是否爲0，爲0時返回。

複雜度分析

取決於進位，近似爲 O(1). 使用了部分額外變量，空間複雜度爲 O(1).