【牛客网】JZ65:不用四则运算符实现两数相加

[TOC]

问题来源

牛客网数据结构题目👉JZ65

题目要求如图

思考

不能使用四则运算，根据过往的学习经历，我唯一能想到的就是位操作符和移位操作符

例：使用位操作符进行int变量交换

位操作符的使用

先来回顾一下位操作符的作用

位操作符操作的是整形的二进制位，它的操作数是2，比较两个整型的二进制位

&按位与：对应的二进制全为1才是1，否则0
|按位或：对应的二进制有1为1，全为0才为0
^按位异或：相同为0，不同为1

比较一下正常的二进制相加和按位异或，发现按位异或是没有进位的相加

原本应该是010，但是按位异或后是000
1+1需要进位的1并没有进到下一位里去

而使用按位与操作符，我们可以得到这两个数相加需不需要进位

0 0 1
0 0 1
//按位与-全1为1
0 0 1
//<< -左移1位
0 1 0

这时候将按位与之后的结果和按位异或相加，就是我们的答案了

但是题目要求不能使用加减

再将按位与的结果0 1 0与按位异或结果0 0 0进行按位与
得到0 0 0，代表无需进位
这时候将0 1 0与0 0 0进行按位异或，即得出相加后的结果0 1 0

这个例子比较简单，我们可以再用复杂一点的例子再证明它的可行性

3：0011和5：0101

操作	结果
1：按位与和左移	0 0 1 0	需要进位
2：按位异或	0 1 1 0
3：1和2按位与，左移	0 1 0 0	需要进位
4：1和2按位异或	0 1 0 0
5：3和4按位与，左移	1 0 0 0	需要进位
6：3和4按位异或	0 0 0 0
7：5和6按位与，左移	0 0 0 0	无需进位
8：5和6按位异或	1 0 0 0	得到结果为8

根据这个思路，我们成功地完成了3和5的相加

代码实现

本题是接口型题目，我们只需要完成一个函数，实现相加的功能

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num1 int整型 
 * @param num2 int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Add(int num1, int num2) 
{
    while(num2)
    {
        int t = (num1 & num2) << 1;
        num1 ^= num2;
        num2 = t;
    }
    return num1;
}