Vgbhfive's Blog

APlusB Solution

Posted on Edited on

A + B问题

这是我在LintCode上看见的一道题目，我觉得很有意思，就决定写了博客记录一下。

题目：
给出两个整数 a 和 b , 求他们的和。

要求：

  1. 不允许使用 + 。
  2. 使用运算符。
  3. a和b都是32位的整数。

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param a: An integer
 * @param b: An integer
 * @return: The sum of a and b 
 */
public int aplusb(int a, int b) {
    if (b == 0) {
        return a;
    }
    int temp1 = a ^ b; //并集
    int temp2 = (a & b) << 1; //交集
        
    return aplusb(temp1, temp2);
}

在我自己解答的过程中，思路很简单：
b 每向右移动一次，a 就向左移动一次，持续直到 b 为0或1的时候，
当b为0 时，直接返回a 。
当b为1 时，返回a & 1。

但是在我看了，网上的解答后，我有点震惊，然后仔细研究了一下。
觉得写这篇博客很有意义。

注：
^ : 异或 (并不是次方符号)