积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

来源

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。链接

1.加法

十进制加法：

13 + 9 = 22 

由于二进制每一位只有0和1两个状态，因此每一位只有四种可能的运算，分别是：

（1）0+0=0；

（2）1+0=1；

（3）0+1=1；

（4）1+1=0；

找规律就能发现，其实就是对每一位进行了异或^操作。只有运算（4）有了进位，由于只有当（1，1）时才有进位，可以用与&操作来保存进位。

这样来拆分这个运算过程：

第一步：

不考虑进位，分别对各位数进行相加，结果为sum：
个位数3加上9为2；十位数1加上0为1； 最终结果为12；

第二步：

只考虑进位，结果为carry：
3 + 9 有进位，进位的值为10；

第三步：

如果步骤2所得进位结果carry不为0，对步骤1所得sum、步骤2所得carry，重复步骤1、 2、3；如果carry为0则结束，最终结果为步骤1所得sum：

• 为什么要循环步骤1、 2、 3直到步骤2所得进位carry等于0？

这是因为有的数做加法时会出现连续进位的情况。

因此，A+B可以先转化为A^B和A&B两个值，由于A&B是进位值，因此需要整体向前移动一位才算进位，如此一来就得到加法的第一步转化公式：A+B=A^B+(A&B)<<1;

具体例子：

//任取两数
num1=13;
num2=11;
 
//二进制
num1:         0 1 1 0 1
num2:         0 1 0 1 1
 
//位运算操作
x=num1^num2 : 0 0 1 1 0
y=num1&num2 : 0 1 0 0 1
 
//因为是进位，y要向前移动一位
y=y<<1      : 1 0 0 1 0
 
//将y当成新的数值继续进行位运算
x2=x^y      : 1 0 1 0 0
y2=x&y      : 0 0 0 1 0
 
y2=y2<<1    : 0 0 1 0 0
 
x3=x2^y2    : 1 0 0 0 0
y3=x2&y2    : 0 0 1 0 0
 
y3=y3<<1    : 0 1 0 0 0
 
//当y=0时结束
x4=x3^y3    : 1 1 0 0 0
y4=x3&y3    : 0 0 0 0 0

当A&B等于0时，说明已经不需要进位了，此时已经得到了正确的值了。

1.1 代码实现

// 递归写法
int add(int num1, int num2){
    if(num2 == 0)
        return num1;
    int sum = num1 ^ num2;
    int carry = (num1 & num2) << 1;
    return add(sum, carry);
}

// 迭代写法
int add(int num1, int num2){
    int sum = num1 ^ num2;
    int carry = (num1 & num2) << 1;  
    while(carry != 0){
        int a = sum;
        int b = carry;
        sum = a ^ b;
        carry = (a & b) << 1;  
    }
    return sum;
}

2.减法

减去一个数，就是加上这个数的相反数。

a-b=a+(-b)
-b=~b+1
a-b=a+(~b+1)

3.乘法

知道了加法运算的位运算实现，那很容易想到乘法运算可以转换成加法运算，被乘数加上乘数倍的自己就行了。还有一个问题就是乘数和被乘数的正负号问题，所以，先处理乘数和被乘数的绝对值的乘积，然后根据它们的符号确定最终结果的符号即可。即：

• 1. 计算绝对值得乘积
• 2. 确定乘积符号（同号为证，异号为负）

代码实现：

/*
* a: 被乘数
* b: 乘数
*/
int multiply(int a, int b){ 
    // 取绝对值　　    
    int multiplicand = a < 0 ? add(~a, 1) : a;    
    int multiplier = b < 0 ? add(~b , 1) : b;// 如果为负则取反加一得其补码，即正数　　    
    // 计算绝对值的乘积　　    
    int product = 0;    
    int count = 0;    
    while(count < multiplier) {        
        product = add(product, multiplicand);        
        count = add(count, 1);// 这里可别用count++，都说了这里是位运算实现加法　　    
    }    
    // 确定乘积的符号　　    
    if((a ^ b) < 0) {// 只考虑最高位，如果a,b异号，则异或后最高位为1；如果同号，则异或后最高位为0；　　　　        
        product = add(~product, 1);    
    }    
    return product;
}

这样做，但是第一步对绝对值作乘积运算我们是通过不断累加的方式来求乘积的，这在乘数比较小的情况下还是可以接受的，但在乘数比较大的时候，累加的次数也会增多，这样的效率不是最高的。需要优化求绝对值的乘积这一步。

模拟现实生活中手动求乘积的过程，这种方式同样适用于二进制，下面以13 * 14为例，演示如何用手动计算的方式求乘数和被乘数绝对值的乘积。

从上图的计算过程可以看出，如果乘数当前位为1，则取被乘数左移一位的结果加到最终结果中；如果当前位为0，则取0加到乘积中（加0也就是什么也不做）。整理后的步骤：

• 1. 判断乘数是否为0，为0跳转至步骤(4)
• 2. 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则相加数为当前被乘数；如果为0，则相加数为0；将相加数加到最终结果中；
• 3. 被乘数左移一位，乘数右移一位；回到步骤(1)
• 4. 确定符号位，输出结果；

3.1 代码实现：

int multiply(int a, int b) {　　
    //将乘数和被乘数都取绝对值　
    int multiplicand = a < 0 ? add(~a, 1) : a; 　　
    int multiplier = b < 0 ? add(~b , 1) : b;　　
    　
    //计算绝对值的乘积　　
    int product = 0;　　
    while(multiplier > 0) {　　　　
        if((multiplier & 0x1) > 0) {// 每次考察乘数的最后一位　　　　
            product = add(product, multiplicand);　　　　
        } 　　　　
        multiplicand = multiplicand << 1;// 每运算一次，被乘数要左移一位　　　　
        multiplier = multiplier >> 1;// 每运算一次，乘数要右移一位（可对照上图理解）　　
    } 　　
    //计算乘积的符号　　
    if((a ^ b) < 0) {　　　　
        product = add(~product, 1);　　
    } 　　
    return product;
}

4.除法

除法运算很容易想到可以转换成减法运算，即不停的用除数去减被除数，直到被除数小于除数时，此时所减的次数就是我们需要的商，而此时的被除数就是余数。这里需要注意的是符号的确定，商的符号和乘法运算中乘积的符号确定一样，即取决于除数和被除数，同号为证，异号为负；余数的符号和被除数一样。

代码实现：

/*
* a : 被除数
* b : 除数
*/
int divide(int a, int b){    
    // 先取被除数和除数的绝对值    
    int dividend = a > 0 ? a : add(~a, 1);    
    int divisor = b > 0 ? a : add(~b, 1);    

    int quotient = 0;// 商    
    int remainder = 0;// 余数    
    // 不断用除数去减被除数，直到被除数小于被除数（即除不尽了）    
    while(dividend >= divisor){// 直到商小于被除数        
        quotient = add(quotient, 1);        
        dividend = substract(dividend, divisor);    
    }    
    // 确定商的符号    
    if((a ^ b) < 0){// 如果除数和被除数异号，则商为负数  
        quotient = add(~quotient, 1);    
    }    
    // 确定余数符号    
    remainder = b > 0 ? dividend : add(~dividend, 1);    
    return quotient;// 返回商
}

这里有和简单版乘法运算一样的问题，如果被除数非常大，除数非常小，那就要进行很多次减法运算。之所以比较慢是因为步长太小，每次只能用1倍的除数去减被除数，所以速度比较慢。

所有的int型数据都可以用[2^0, 2^1,…，2³¹]这样一组基来表示（int型最高31位）。不难想到用除数的2³¹,2³⁰,…,2,1倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。
2的i次方就相当于左移i位，至于为什么从31位开始呢？因为int型数据最大值就是2³¹。

4.1 代码实现：

int divide_v2(int a,int b) {   
    // 先取被除数和除数的绝对值    
    int dividend = a > 0 ? a : add(~a, 1);    
    int divisor = b > 0 ? a : add(~b, 1);    
    int quotient = 0;// 商    
    int remainder = 0;// 余数    
    for(int i = 31; i >= 0; i--) {
        //比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用(dividend>>i)与divisor比较，
        //效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor       
        if((dividend >> i) >= divisor) {            
            quotient = add(quotient, 1 << i);            
            dividend = substract(dividend, divisor << i);        
        }    
    }    
    // 确定商的符号    
    if((a ^ b) < 0){
        // 如果除数和被除数异号，则商为负数        
        quotient = add(~quotient, 1);    
    }    
    // 确定余数符号    
    remainder = b > 0 ? dividend : add(~dividend, 1);    
    return quotient;// 返回商
}