题目

LintCode:A+B问题

描述

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。

• 说明
  a和b都是 32位 整数么？
  是的
  我可以使用位运算符么？
  当然可以

样例

如果a=1并且 b=2，返回3

思路

题目要求不可以使用加减乘除四则运算，那肯定是在移位或者位运算上做文章。经过分析，两个整数a和b的加法操作，可以等效于(a&b)<<1和a^b相加，也就是进位值和非进位值，然后又可以继续通过这种操作进行运算，直到达到一个不满足的条件（也就是不在进位）为止。这就可以借助循环或者递归操作，关键在于找到结束循环和递归的条件。对于a&b来说，显然是有可能不在进位，也就是值为0的，这就是一个有效的判断条件。

实现

递归实现

1. java代码

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        
        if(a == 0)
            return b;
        return aplusb((a&b)<<1, a ^ b);
    }
};

2. 结果分析
   结果：结果通过了LintCode的要求。
   分析：这种递归只是单纯两个整数的操作，在若干次递归运算之后，很快达到某个操作数为0的条件，从而结束递归。因此速度还是可以达到要求。

非递归实现

1. java代码

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        
        int sum = 0;
        do {
            sum = a ^ b;
            a = (a & b) << 1;
            b = sum;
        } while ( a != 0 );
        
        return sum;
    }
};

2.结果分析
结果：结果通过了LintCode的要求。
分析：这种操作需要完全理解实现原理。加法，可以拆分成异或得到的“加法不进位”与相与左移1的进位的加法，因此，每次递归中都进行异或、相与左移1，然后，将得到的结果再做同样的操作，直到进位为0，递归停止。

其它优化参考

lintcode刷题 A + B 问题 位运算

思路：
考虑一个普通的加法计算：5＋17＝22
在十进制加法中可以分为如下3步进行：
忽略进位，只做对应各位数字相加，得到12（个位上5＋7＝12，忽略进位，结果2）；
记录进位，上一步计算中只有个位数字相加有进位1，进位值为10；
按照第1步中的方法将进位值与第1步结果相加，得到最终结果22。
下面考虑二进制数的情况（5＝101，17＝10001）：
仍然分3步：
忽略进位，对应各位数字相加，得到10100；
记录进位，本例中只有最后一位相加时产生进位1，进位值为10（二进制）；
按照第1步中的方法将进位值与第1步结果相加，得到最终结果10110，正好是十进制数22的二进制表示。
接下来把上述二进制加法3步计算法用位运算替换：
第1步（忽略进位）：0＋0＝0，0＋1＝1，1＋0＝0，1＋1＝0，典型的异或运算。
第2步：很明显，只有1＋1会向前产生进位1，相对于这一数位的进位值为10，而10＝(1&1)<<1。
第3步：将第1步和第2步得到的结果相加，其实又是在重复这2步，直到不再产生进位为止。

题目

LintCode:斐波纳契数列

描述

查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第i-1个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例

给定 1，返回 0
给定 2，返回 1
给定 10，返回 34

实现

递归实现

1. java代码

class Solution {
    public int fibonacci(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

2. 结果分析
   结果：结果不尽人意，速度非常慢，甚至没有通过 LintCode 的评测。
   分析：这种递归不同于一般的递归，在n较大时，两次递归调用中存在大量的重复运算，导致速度非常慢。

非递归实现

1. java代码

class Solution {
    public int fibonacci(int n) {
        if(1==n)
            return 0;
        if(2==n)
            return 1;
        int a=0;
        int b=1;
        int sum=0;
        while(n>2)
        {
            sum=a+b;
            a=b;
            b=sum;
            n--;
        }
        return sum;
    }
}

2. 结果分析
   结果：经测试 C++ 最快可以以 10ms 轻松通过 LintCode 的评测。
   分析：时间复杂度为 o(n) ，空间复杂度为 o(1) ，效果不错。
   细节：使用 while 代替 for 节省了一个 Int(4Byte) 的空间。

其它优化参考

斐波纳契数列实现及优化