A Plus B

题目描述

Write a function that add two numbers A and B. You should not use + or any arithmetic operators.

解题方法

if you know binary arithmetic or how to add numbers in binary format

  • you may be familiar with fact than sum of two numbers can be obtained by using XOR operation
  • carry, by using AND operation.

Iterative solution

public static int addTwoIntegers(int a, int b){
    while (b != 0){
        int carry = (a & b); // Carry is AND of two bits
        a = a ^ b // sum of tw obits is A XOR B
        b = carry << 1 //shifts carry to 1 bit to calculate sum 
    }
}

Recursive Solution

public static int addTwoIntegers(int a, int b){
    if (b == 0){
        return a;
    }
    int sum = a ^ b;
    int carry = (a & b) << 1;
    return addTwoIntegers(sum, carry);
}

bit manipulation的解释

  1. a & b能够得到现在的carry

因为只有在同一位都是1的时候才会产生carry, 所以a & b能够得到每一位是否会产生carry.

下面的<< 1就是将carry左移一位放到下一次的计算中去

  1. a ^ b 能够得到除了carry的sum

  2. 0 + 1 = 1

  3. 1 + 1 = 0 + carry
  4. 1 + 0 = 1
  5. 0 + 0 = 0

由上面的公式可以看出XOR可以得到当前位的sum的结果

这个方法对于python不行，因为python不会overflow而省去,不过可以加些code使它work

Reference