“A + B”竟然还能这样做？

首先我们来看一下这道题目：

相信许多人对这道题目并不陌生，在刚开始学习编程的时候，我们总能在习题库中看到它，如何解决呢，代码很简单：

#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d
",a+b);
    return 0;
}

但今天在逛博客的时候发现了领扣的一道有意思的题目，不使用加法运算符，计算a+b的值？

作为一名初学者，我对此题毫无思路，但后来在思考的过程中，我想到了一种特殊的运算符 ——位运算

那么，用位运算，这道题目该怎么解决呢？别着急，咱们接着往下看。

首先，需要认识四个位运算符(大佬请无视）

&: 按位与运算，使参与运算的两数各对应的二进位相与，只有对应的两个二进制位均为1时，结果才为1，否则为0.

　　举个栗子：a = 1, b = 2;

　　　　　　　　a & b = 0001 & 0010 = 0000 = 0

^: 按位异或运算，使参与运算的两数各对应的二进位相异或，当两对应的二进位不同时，结果为1，否则为0.

　　举个栗子：a = 9, b = 5;

　　　　　　　　a ^ b = 00001001 ^ 00000101 = 00001100 = 12;

<< : 左移运算符：左移n位就是乘以2的n次方，作用是把“<<”左边的运算数的各二进位全部左移若干位，由“<<”右边的数指定移动的位数，高位丢弃，低位补0。

　　举个栗子: 3 << 4

　　　　　　　　 00000011 << 4 = 00110000 = 48;

>> : 右移运算符: 右移n位就是除以2的n次方, 作用是把“>>”左边的运算数的各二进位全部右移若干位，“>>”右边的数指定移动的位数.

　　举个栗子: 15 >> 2 = 00001111 = 00000011;　　　　　　　　

　好，了解完基础知识过后，咱们开始正式解题：

　　首先，咱们观察一下，1 ^ 0 = 1, 1 ^ 2 = 3,

　　　　　　　　　　　　 2 ^ 3 = 1,

　　　　　　　　　　　　 3 ^ 4 = 7,

　　　　　　　　　　　　 4 ^ 5 = 1, 5 ^ 6 = 3, 6 ^ 7 = 1,

　　　　　　　　　　　　 7 ^ 8 = 15 ... ... ... ...

　　采用异或进行运算，通过这几组测试，多多少少有一些不合群的，得不到正确的结果，

　　分析一下 2 ^ 3 = 0011 ^ 0010 = 0001,如果第二位变成1，那就变为5了

　　　　　　 4 ^ 5 = 0100 ^ 0101 = 0001,第一位变成1，那不就变成9了

　　慢慢总结就会发现，其实它存在着一定的进位关系：　

那么加法运算可以这样实现：

　　1）先不考虑进位，按位计算各位累加（用异或实现），得到值a；

　　2）然后在考虑进位，并将进位的值左移，得值b，若b为0，则a就是加法运算的结果，若b不为0，则a+b即得结果（递归调用该函数）。

　　代码如下:

int add(int a, int b)
{
    if(b == 0)
        return a;
    int c = a ^ b;
    int j = (a & b) << 1;
    return add(c, j);
}

参考：