Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5cc674a

Browse files
committed
Fix leetcode daily problem
1 parent2c392ae commit5cc674a

File tree

2 files changed

+82
-21
lines changed

2 files changed

+82
-21
lines changed

‎leetcode-solutions/0371-两整数之和.mdrenamed to‎leetcode-solutions/0371-Sum-Of-Two-Integers-两整数之和.md

Lines changed: 81 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -2,91 +2,152 @@
22

33
##题解
44

5+
6+
57
题目要求不能使用 $+、-$​，自然想到使用其他的二元运算符，我们可以根据二进制位，选择位运算符计算得到两数之和。
68

7-
###两个二进制位相加有以下四种情况
9+
**二进制相加，思想类似于十进制加法，但从「逢十进一」变为 「逢二进一」。**
10+
11+
**两个二进制位相加有以下四种情况。**
812

913
```
1014
1 + 1 = 0 (进位)
15+
1116
1 + 0 = 1
17+
1218
0 + 1 = 1
19+
1320
0 + 0 = 0
21+
1422
```
1523

16-
直接使用异或 ​^ 运算符的话，需要额外处理 两个二进制位都为1 的情况。
24+
25+
26+
直接使用异或 ^ 运算符的话，需要额外处理进位的情况， 即两个二进制位都为1。
1727

1828
我们可以使用 bit位为进位符，来判断这种情况。
1929

20-
下面考虑 bit进位符，如何和两个二进制位相加相结合。
30+
下面考虑bit进位符，两个二进制位如何相加。
31+
32+
2133

2234
**假设现在统计到二进制的第 i 位。**
2335

2436
```
2537
bit = 0 的情况
2638
27-
二进制位相加 运算后结果
2839
29-
1 + 1 = 0 (进位) --> 答案加 0 bit=1
30-
1 + 0 = 1 --> 答案加 2^i bit=0
31-
0 + 1 = 1 --> 答案加 2^i bit=0
32-
0 + 0 = 0 --> 答案加 2^i bit=0
40+
41+
二进制位相加 运算后结果
42+
43+
44+
45+
1 + 1 = 0 (进位) --> 答案加 0 bit=1
46+
47+
1 + 0 = 1 --> 答案加 2^i bit=0
48+
49+
0 + 1 = 1 --> 答案加 2^i bit=0
50+
51+
0 + 0 = 0 --> 答案加 2^i bit=0
52+
3353
```
3454

55+
56+
3557
```
3658
bit = 1 的情况
3759
38-
二进制位相加 运算后结果
60+
61+
62+
二进制位相加 运算后结果
63+
64+
3965
4066
1 + 1 = 0 (进位) --> 答案加 2^i bit=1
41-
1 + 0 = 1 --> 答案加 0 bit=1
42-
0 + 1 = 1 --> 答案加 0 bit=1
43-
0 + 0 = 0 --> 答案加 2^i bit=0
44-
```
4567
46-
、
68+
1 + 0 = 1 --> 答案加 0 bit=1
69+
70+
0 + 1 = 1 --> 答案加 0 bit=1
71+
72+
0 + 0 = 0 --> 答案加 2^i bit=0
4773
48-
数据范围是 $-1000<=x<=1000$，如果没有负数，根据二进制位，我们只需要统计10个二进制位，因为 $2^{10}=1024>100$​。
74+
```
75+
76+
数据范围是 $-1000<=x<=1000$，如果没有负数，根据二进制位，我们只需要统计10个二进制位，因为 $2^{10}=1024>100$。
4977

5078
有负数的情况，我们需要统计到最高位，判断是否为负数，因此要统计32位。
5179

5280
时间复杂度: $O(C)$ C为常数32。
5381

54-
空间复杂度: O(1)。
55-
82+
空间复杂度: $O(1)$。
5683

5784
##代码
5885

86+
87+
5988
```c++
6089
classSolution {
90+
6191
public:
92+
6293
int getSum(int a, int b) {
94+
6395
int ans = 0, bit = 0;
96+
6497
for (int i = 0; i < 32; i++) {
98+
6599
int x = (a >> i) & 1, y = (b >> i) & 1;
66-
if (x == 1 && y == 1) {
100+
101+
if (x & y) {
102+
67103
ans |= (bit << i);
104+
68105
bit = 1;
106+
69107
} else if (x | y) {
108+
70109
ans |= (1 ^ bit) << i;
110+
71111
} else {
112+
72113
ans |= (bit << i);
114+
73115
bit = 0;
116+
74117
}
118+
75119
}
120+
76121
return ans;
122+
77123
}
124+
78125
};
126+
79127
```
80128

129+
81130
##最后
82131

132+
133+
83134
大家好，我是编程熊，字节跳动、旷视科技前员工，ACM亚洲区域赛金牌，欢迎[关注我](https://leetcode-cn.com/u/bianchengxiong/) 和加入[LeetCode组队刷题群](https://mp.weixin.qq.com/s/TsTcCDboXwnTnUeIW3Zg9Q)。
84135

85-
分享几篇算法超级易懂的文章，希望对你有所帮助
136+
137+
138+
**分享几篇算法超级易懂的文章，希望对你有所帮助**
86139

87140
1、[ACM金牌选手讲解LeetCode算法《线性表》](https://mp.weixin.qq.com/s/qwaYOFIksFVqZtA_nisl6g)
141+
88142
2、[ACM金牌选手讲解LeetCode算法《栈和队列的高级应用》](https://mp.weixin.qq.com/s/I3DQOUmABmWav4nrAiI3Fg)
143+
89144
3、[ACM金牌选手讲解LeetCode算法《哈希表》](https://mp.weixin.qq.com/s/af4gvYURUoCTfsyzsI9Www)
90-
4、[ACM金牌选手讲解LeetCode算法《二叉树》](https://mp.weixin.qq.com/s/8AcRNQS0Nno2_fU6kMtZeQ)
145+
146+
4、[ACM金牌选手讲解LeetCode算法《二叉树》](https://mp.weixin.qq.com/s/8AcRNQS0Nno2_fU6kMtZeQ)
147+
148+
5、[编程熊讲解LeetCode算法《堆》](https://mp.weixin.qq.com/s/ggd42G_QJ6I43F-vXSbpdA)
149+
150+
91151

92152
如果题解和文章对你有所帮助，欢迎**点赞**支持。
153+

‎力扣LeetCode题解/0371-Sum-Of-Two-Integers-两整数之和.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55

66

7-
题目要求不能使用 $+、-$，自然想到使用其他的二元运算符，我们可以根据二进制位，选择位运算符计算得到两数之和。
7+
题目要求不能使用 $+、-$​，自然想到使用其他的二元运算符，我们可以根据二进制位，选择位运算符计算得到两数之和。
88

99
**二进制相加，思想类似于十进制加法，但从「逢十进一」变为 「逢二进一」。**
1010

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp