
-
近期文章
近期评论
- Jimmyho发表在《LeetCode 八月签到题》
- inspiraton发表在《LeetCode 八月签到题》
- Jimmyho发表在《围炉夜话》
- Jimmyho发表在《围炉夜话》
- Jimmyho发表在《围炉夜话》
题目:写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
思考过程:想了很久…考虑过乘方和对数运算,无解
解答:题目考点在于发散性思维和位运算
思路:
首先看十进制是如何做的: 5+7=12,
三步走 第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,
那么第一步得到的值就是最终结果。
第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。
编程中使用位运算编译器自动默认数为二进制形式,无需特别转化。
故同样我们可以用三步走的方式计算二进制值相加:
举例: 5对应二进制101,7对应二进制111
第一步:相加各位的值,不算进位,得到010,记为未相加进位值的结果(value)
在二进制中:考虑不同情况相加后的最终结果:
0+1=1+0=0+0=0, 1+1=0
由此根据结果我们联想到二进制每位相加就相当于各位做异或操作,即计算101^111。
第二步:计算进位值,同理,在二进制中:考虑不同情况相加后的最终进位结果,记为(cal):
0+1=1+0=0+0=0, 1+1=1
由此根据结果我们联想到二进制每位进位结果计算就相当于各位做与操作,与十进制同理,数值整体要大一位,十进制*10,二进制故为*2,故再向左移一位得到1010,操作位:(101&111)<<1。
第三步:重复上述两步, 因为结果(记为result)=进位值+未相加进位值的结果,如果仍需进位,即进位值!=0,得出的两个数还要相加,故进行递归循环相加运算直至无需进位。
代码实现:
class
Solution {
public
:
int
Add(
int
num1,
int
num2)
{
int
cal=num2;
int
value=num1;
int
result=num1;
while
(cal!=0)
{
result=cal^value;
cal=(value&cal)<<1;
value=result;
}
return
result;
}
};
由于是磕磕绊绊,修修改改的结果,还是太啰嗦了,dalao的简洁示例
public
class
Solution {
public
int
Add(
int
num1,
int
num2) {
while
(num2!=
0
) {
int
temp = num1^num2;
num2 = (num1&num2)<<
1
;
num1 = temp;
}
return
num1;
}
}
想了一会,理解了加法递归过程后能给出更优雅的代码:
class Solution {
public:
int Add(int num1, int num2)
{
if(num2==0)
return num1;
else
return Add(num1^num2, (num1&num2)<<1);
}
};
甚至可以用更加优雅的布尔表达式搞一行流:
return
num2 ? Add(num1^num2, (num1&num2)<<1) : num1;
位运算的扩展使用:
Q:如何不用中间变量实现两个数的交换
A:两种方法:
1. a=a+b; b=a-b;a=a-b;(加减乘除
2. a=a^b;b=a^b;a=a^b;(异或运算
以上。睡觉。
Stay Hungry,Stay Foolish.
Copyright © 2021 Jimmy和他的朋友们. 自豪地采用 WordPress。 黑酷由Iceable Themes所设计。