A plus B Problem

Question

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

题解

不用加减法实现加法，类似数字电路中的全加器，异或求得部分和，相与求得进位，最后将进位作为加法器的输入，典型的递归实现思路。

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.         }
  15.         return result;
  16.     }
  17. }

源码分析

递归步为进位是否为0，为0时返回。

复杂度分析

取决于进位，近似为 O(1). 使用了部分额外变量，空间复杂度为 O(1).