code4offer-9 不用加减乘除做加法

不用加减乘除做加法

问题描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

分析

使用位运算，计算机内部就是用门电路做运算的

^ 可以看作是 无进位加法

1
2
3
4
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

&可以用来计算进位，需要左移一位

1
2
3
4
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
1
2
3
4
5
6
7
8
9
10
11
11 + 01 = 100

sum = 11 ^ 01 = 10
carry = (11 & 01) << 1 = 10

// 对sum和carry继续使用位运算做加法

sum = 10 ^ 10 = 00
carry = (10 & 10) << 1 = 100

// sum为0 已经不用再计算了，最终结果为sum|carry
1
2
3
4
5
6
7
8
9
10
11
12
13
int Add(int num1, int num2)
{
    int sum = num1 ^ num2, carry = (num1 & num2) << 1;

    while (carry & sum){
        num1 = sum;
        num2 = carry;
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
    }

    return sum|carry;
}

Reference

1.位运算加法 - 简书