题目描述:
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
要完成的函数:
int getSum(int a, int b)
说明:
1, 这道题目其实要实现二进制的加法, 我们可以用异或实现, 十分简单.
代码如下:
- int getSum(int a, int b)
- {
- int a1,b1,res1,result=0;
- bool addflag=0;
- for(int i=0;i<32;i++)
- {
- a1=a&1;// 取出最低位
- b1=b&1;// 取出最低位
- res1=a1^b1^addflag;// 用异或计算加完的结果
- if(a1==0&&b1==0)// 判断 addflag
- addflag=0;
- else if(a1==0&&b1==1&&addflag==0)
- addflag=0;
- else if(a1==0&&b1==1&&addflag==1)
- addflag=1;
- else if(a1==1&&b1==0&&addflag==0)
- addflag=0;
- else if(a1==1&&b1==0&&addflag==1)
- addflag=1;
- else
- addflag=1;
- result+=(res1<<i);
- a>>=1;//a 不断向右移动一位 (二进制)
- b>>=1;//b 不断向右移动一位 (二进制)
- }
- return result;
- }
异或就是二进制的王道运算方法.
上述代码实测 3ms, 有很多人实现了 2ms 的做法, 看来还有优化的空间.
2, 上述代码中比较费时间的也就是大堆的 if else 语句了.
其实我们要判断的是如下条件:
a1 | b1 | 上个 addflag | 新的 addflag |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
有没有觉得很熟悉, 出现了 1 个 1, 结果是 0, 出现了 2 个 1, 结果是 1.
我们可以用异或来更加快速地处理.
至于全是 0 和全是 1 的情况, 就特殊处理好了.
代码如下:
- int getSum(int a, int b)
- {
- int a1,b1,res1,result=0;
- bool addflag=0;
- for(int i=0;i<32;i++)
- {
- a1=a&1;
- b1=b&1;
- res1=a1^b1^addflag;
- if(a1==1&&b1==1&&addflag==1)
- addflag=1;
- else if(a1==0&&b1==0&&addflag==0)
- addflag=0;
- else
- addflag=!(a1^b1^addflag);
- result+=(res1<<i);
- a>>=1;
- b>>=1;
- }
- return result;
- }
上述代码实测 2ms,beats 100% of cpp submissions.
3, 比较 1 中和 2 中代码, 为什么异或做的条件判断可以比 if else 语句更省时间?
因为 if else 语句要不断尝试, 这个 if 不满足, 那就再尝试 else if, 如果再不满足, 就再尝试下一个 else if, 不断地尝试过程浪费了一些时间.
而且尝试过程是 a1 跟 0,b1 跟 0,addflag 跟 0 这些值在比较, 比较过程其实也就是相减, 看会不会最终结果为 0. 所以其实还是在做运算.
异或的做法直接就是三个值做异或运算, 一次搞定, 所以肯定比 if else 语句快.
来源: http://www.bubuko.com/infodetail-2565414.html