剑指Offer-65.不用加减乘除做加法

Posted on | In

面试题65. 不用加减乘除做加法

先来说下什么是异或，以及异或的特点。

参与运算的两个值，如果相对应的位相同，则为0，否则为1。

例如：1100 ^ 0011 = 0000

异或有三个性质：

  1. 0异或任何数 = 任何数
  2. 任何数异或任何数 = 0
  3. 数a两次异或同一个数b(a = a ^ b ^ b)仍为a

^异或相当于无进位的求和，如十进制中 9 + 1 = 10，无进位的求和的值就是等于0，而非10。

9 ^ 1 ==> 1001 ^ 0001 = 1000

&相当于求每位的进位数： 9 & 1 ==> 1001 & 0001 = 0001 如果进位的话，

9 + 1 = 10 ==> (9^ 1) ^ (9 & 1 << 1) ==> (1000) ^ (0010) = 1010 1010 == 10

所以得出的结论是+法可以用 &^组合使用得到: a + b = (a^b)^(a&b<<1 )

在计算的时候为了避免例如99 + 1 进位两次，所以运算的完一次要再判断 a&b 的值是否为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int add(int a, int b) {
        // (a^b) & ((a&b)<<1)  != 0
        // (a^b) ^ ((a&b)<<1)
        int tmp = 0;
        while(b != 0){
            tmp = a ^ b;
            b = (unsigned)(a&b)<<1;
            a = tmp;
        }
        return a;
    }
};