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
Appearance settings

Expand file tree

/

A+B.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
84 lines (65 loc) · 2.19 KB
/

A+B.java

Copy path

File metadata and controls

executable file
·
84 lines (65 loc) · 2.19 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
E
^ 是不完全加法. 每次都忽略了进位。而 & 刚好可以算出需要的所有进位。
那么就，首先记录好进位的数字：carry. 然后 a^b 不完全加法一次。然后b用来放剩下的carry, 每次移动一位，继续加，知道b循环为0为止。
在第一回 a ^ b 之后, b 的作用就消失了. 接下去应该给parameter重新命名.
sum = a ^ b; // sum without adding carries
nextCarry = (a & b) << 1;
用其他variable name 取代 a, b 会更好理解一点.
Bit Operation
Steps:
a & b: 每bit可能出现的余数
a ^ b: 每bit在此次操作可能留下的值，XOR 操作
每次左移余数1位，然后存到b, 再去跟a做第一步。loop until b == 0
(http://www.meetqun.com/thread-6580-1-1.html)
```
/*
Also on LeetCode: Sum of Two Integers
Write a function that add two numbers A and B. You should not use + or any arithmetic operators.
Example
Given a=1 and b=2 return 3
Note
There is no need to read data from standard input stream. Both parameters are given in function aplusb, you job is to calculate the sum and return it.
Challenge
Of course you can just return a + b to get accepted. But Can you challenge not do it like that?
Clarification
Are a and b both 32-bit integers?
Yes.
Can I use bit operation?
Sure you can.
Tags Expand
Cracking The Coding Interview Bit Manipulation
*/
/*
Thoughts:
Wring down truth table for a and b:
a + b on each bit becomes OR operation, exception when they are both 1, where they becomes 0 and add forward to next bit.
- We can use a carryOver
- Use long to hold the result
*/
class Solution {
public int getSum(int a, int b) {
int sum = a ^ b; // incomplete sum
int nextCarry = (a & b) << 1;
while (nextCarry != 0) {
int currentCarry = sum & nextCarry;
sum = sum ^ nextCarry;
nextCarry = currentCarry << 1;
}
return sum;
}
}
/*
Thought:
Bit operation. Just to remmeber this problem, doing A+B using bit.
*/
class Solution {
public int aplusb(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
};
```
Morty Proxy This is a proxified and sanitized view of the page, visit original site.