###### tags: `leetcode`
# #371 Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = -2, b = 3
Output: 1
## python3 sum()
```python=
class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
return sum([a, b])
```
## Bitwise operation on C
try to use C to do bitwise
- `&`
- bitwise AND
- `|`
- bitwise inclusive OR
- `^`
- bitwise XOR (eXclusive OR)
- `<<`
- left shift
- `>>`
- right shift
- `~`
- bitwise NOT (one's complement) (unary)
### use the fact that `2's complement=1's complement+1`
#### reference
http://puremonkey2010.blogspot.com/2011/05/c-bitwise-operation.html
#### A simple test
```cpp=
#include<stdio.h>
int addone(int);
int minusone(int);
int main() {
for (int i = 0; i < 10; i = addone(i)) {
printf("%d", i);
}
for (int i = 9; i > -1; i = minusone(i)) {
printf("%d", i);
}
}
int addone(int x) {
return -~x; // x + 1
}
int minusone(int x) {
return ~-x; // x - 1
}
```
### try 0
```cpp=
int addone(int);
int minusone(int);
int getSum(int a, int b){
if (b >= 0) {
for (int i = 0; i < b; i = addone(i)) {
a = addone(a);
}
}
if (b < 0) {
for (int i = 0; i < -b; i = addone(i)) {
a = minusone(a);
}
}
return a;
}
int addone(int x) {
return -~x; // x + 1
}
int minusone(int x) {
return ~-x; // x - 1
}
```
:::danger
Line 12: Char 29: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.c)
:::
:::info
Last executed input
2147483647
-2147483648
:::
#### Overflow
-2147483648 is the under-bound of 32-bit int.
Nevigation if it leads to 2147483648, and this is over the upper-bound of 32-bit int (214748364).
##### Revision
In the for-loop, void using `-b`.
### try 1
#### Do experiment
```cpp=
#include <stdio.h>
#include <stdlib.h>
int getSum(int, int);
int addone(int);
int minusone(int);
int main(){
int a = 2147483647;
int b = -2147483648;
// int a = -5;
// int b = -2;
printf("%d", getSum(a,b));
}
int getSum(int a, int b){
printf("a = %d\n",a);
printf("b = %d\n",b);
if (b >= 0) {
for (int i = 0; i < b; i = addone(i)) {
a = addone(a);
//printf(" a = %d\n",a);
}
}
if (b < 0) {
//for (int i = 0; i < -b; i = addone(i)) {
for (int i = b; i < 0; i = addone(i)) {
a = minusone(a);
//printf(" a = %d\n",a);
}
}
return a;
}
int addone(int x) {
return -~x; // x + 1
}
int minusone(int x) {
return ~-x; // x - 1
}
```
:::warning
int a = 2147483647;
int b = -2147483648;
is too large for some online compiler
:::
#### LeetCode
```cpp=
int addone(int);
int minusone(int);
int getSum(int a, int b){
if (b >= 0) {
for (int i = 0; i < b; i = addone(i)) {
a = addone(a);
}
}
if (b < 0) {
for (int i = b; i < 0; i = addone(i)) {
a = minusone(a);
}
}
return a;
}
int addone(int x) {
return -~x; // x + 1
}
int minusone(int x) {
return ~-x; // x - 1
}
```
:::success
Runtime: 1200 ms, faster than 5.54% of C online submissions for Sum of Two Integers.
Memory Usage: 6.8 MB, less than 12.84% of C online submissions for Sum of Two Integers.
:::
### try 2
Try to improve runtime.
Use the idea here
https://leetcode.com/problems/sum-of-two-integers/discuss/84305/Share-my-C%2B%2B-solutionseasy-to-understand
The main idea is to add a and b to c, without considering carry.
Then add c and carry, recursively, until no carry.
```cpp=
int getSum(int a, int b){
int direct_sum_without_carry = a ^ b; // XOR
int carry = a & b; // AND
while (carry != 0){
a = direct_sum_without_carry;
b = carry;
direct_sum_without_carry = a ^ b; // XOR
carry = a & b; // AND
}
int direct_sum_with_all_carry = direct_sum_without_carry;
return direct_sum_with_all_carry;
}
```
:::danger
Wrong Answer
Input
2
3
Output
3
Expected
5
:::
:::warning
I didn't do the left-shift
:::
### try 3
```cpp=
int getSum(int a, int b){
int direct_sum_without_carry = a ^ b; // XOR
int carry = a & b; // AND
while (carry != 0){
a = direct_sum_without_carry;
b = carry << 1;
direct_sum_without_carry = a ^ b; // XOR
carry = a & b; // AND
}
int direct_sum_with_all_carry = direct_sum_without_carry;
return direct_sum_with_all_carry;
}
```
:::danger
Line 6: Char 19: runtime error: left shift of 1073741824 by 1 places cannot be represented in type 'int' (solution.c)
:::
:::danger
Last executed input
-1
1
:::
#### Reason of failure
1073741824 = 2^30
= 01000000000000000000000000000000
A left-shift of 1073741824 leads to 2^31 and thus overflow.
Recall that the upper bound of (signed) integer is 2^31-1.
#### Revision
I have to consider minus number and overflow.
##### experiment
Environment is on https://www.onlinegdb.com/online_c_compiler
```cpp=
#include <stdio.h>
void print2(int x) {
for (int c = 31; c >= 0; c--) {
int k = x >> c;
if (k & 1)
printf("1");
else
printf("0");
}
printf("\n");
}
int getSum(int a, int b){
int direct_sum_without_carry = a ^ b; // XOR
printf("before the while; XOR; direct_sum_without_carry %d\n", direct_sum_without_carry);
print2(direct_sum_without_carry);
int carry = a & b; // AND
printf("before the while; AND; carry %d\n", carry);
print2(carry);
while (carry != 0){
a = direct_sum_without_carry;
b = carry << 1;
direct_sum_without_carry = a ^ b; // XOR
printf(" direct_sum_without_carry %12d ", direct_sum_without_carry);
print2(direct_sum_without_carry);
carry = a & b; // AND
printf(" carry %12d ", carry);
print2(carry);
}
int direct_sum_with_all_carry = direct_sum_without_carry;
return direct_sum_with_all_carry;
}
int main() {
int a = -1;
int b = 1;
printf("%d\n", getSum(a,b));
return 0;
}
```
This will work. It overflows and go back to 1.
```typescript=
before the while; XOR; direct_sum_without_carry -2
11111111111111111111111111111110
before the while; AND; carry 1
00000000000000000000000000000001
direct_sum_without_carry -4 11111111111111111111111111111100
carry 2 00000000000000000000000000000010
direct_sum_without_carry -8 11111111111111111111111111111000
carry 4 00000000000000000000000000000100
direct_sum_without_carry -16 11111111111111111111111111110000
carry 8 00000000000000000000000000001000
direct_sum_without_carry -32 11111111111111111111111111100000
carry 16 00000000000000000000000000010000
direct_sum_without_carry -64 11111111111111111111111111000000
carry 32 00000000000000000000000000100000
direct_sum_without_carry -128 11111111111111111111111110000000
carry 64 00000000000000000000000001000000
direct_sum_without_carry -256 11111111111111111111111100000000
carry 128 00000000000000000000000010000000
direct_sum_without_carry -512 11111111111111111111111000000000
carry 256 00000000000000000000000100000000
direct_sum_without_carry -1024 11111111111111111111110000000000
carry 512 00000000000000000000001000000000
direct_sum_without_carry -2048 11111111111111111111100000000000
carry 1024 00000000000000000000010000000000
direct_sum_without_carry -4096 11111111111111111111000000000000
carry 2048 00000000000000000000100000000000
direct_sum_without_carry -8192 11111111111111111110000000000000
carry 4096 00000000000000000001000000000000
direct_sum_without_carry -16384 11111111111111111100000000000000
carry 8192 00000000000000000010000000000000
direct_sum_without_carry -32768 11111111111111111000000000000000
carry 16384 00000000000000000100000000000000
direct_sum_without_carry -65536 11111111111111110000000000000000
carry 32768 00000000000000001000000000000000
direct_sum_without_carry -131072 11111111111111100000000000000000
carry 65536 00000000000000010000000000000000
direct_sum_without_carry -262144 11111111111111000000000000000000
carry 131072 00000000000000100000000000000000
direct_sum_without_carry -524288 11111111111110000000000000000000
carry 262144 00000000000001000000000000000000
direct_sum_without_carry -1048576 11111111111100000000000000000000
carry 524288 00000000000010000000000000000000
direct_sum_without_carry -2097152 11111111111000000000000000000000
carry 1048576 00000000000100000000000000000000
direct_sum_without_carry -4194304 11111111110000000000000000000000
carry 2097152 00000000001000000000000000000000
direct_sum_without_carry -8388608 11111111100000000000000000000000
carry 4194304 00000000010000000000000000000000
direct_sum_without_carry -16777216 11111111000000000000000000000000
carry 8388608 00000000100000000000000000000000
direct_sum_without_carry -33554432 11111110000000000000000000000000
carry 16777216 00000001000000000000000000000000
direct_sum_without_carry -67108864 11111100000000000000000000000000
carry 33554432 00000010000000000000000000000000
direct_sum_without_carry -134217728 11111000000000000000000000000000
carry 67108864 00000100000000000000000000000000
direct_sum_without_carry -268435456 11110000000000000000000000000000
carry 134217728 00001000000000000000000000000000
direct_sum_without_carry -536870912 11100000000000000000000000000000
carry 268435456 00010000000000000000000000000000
direct_sum_without_carry -1073741824 11000000000000000000000000000000
carry 536870912 00100000000000000000000000000000
direct_sum_without_carry -2147483648 10000000000000000000000000000000
carry 1073741824 01000000000000000000000000000000
direct_sum_without_carry 0 00000000000000000000000000000000
carry -2147483648 10000000000000000000000000000000
direct_sum_without_carry 0 00000000000000000000000000000000
carry 0 00000000000000000000000000000000
0
```
##### Question
I want to know how to determine that there will be 32 bits.
By `sizeof(int)`, I get a `4`, which is 16 bits.
https://hackmd.io/kzk9OFoYSPGLEO6A0wq9KA
### try 4
Edit from
`b = carry << 1;`
to
`b = (carry & 0xffffffff) << 1;`
Then it works!
```cpp=
int getSum(int a, int b){
int direct_sum_without_carry = a ^ b; // XOR
int carry = a & b; // AND
while (carry != 0){
a = direct_sum_without_carry;
b = (carry & 0xffffffff) << 1;
direct_sum_without_carry = a ^ b; // XOR
carry = a & b; // AND
}
int direct_sum_with_all_carry = direct_sum_without_carry;
return direct_sum_with_all_carry;
}
```
:::success
Success
Runtime: 0 ms, faster than 100.00% of C online submissions for Sum of Two Integers.
Memory Usage: 6.7 MB, less than 19.59% of C online submissions for Sum of Two Integers.
:::
I don't why use `b = (carry & 0xffffffff) << 1;` can avoid the error from try 3 on Leetcode.
>Line 6: Char 19: runtime error: left shift of 1073741824 by 1 places cannot be represented in type ‘int’ (solution.c)
>
`0xffffffff` is merly 32 1's.
It seem like if I use `carry & 0xffffffff` then I can do operations with overflows.
### try 5
```cpp=
int getSum(int a, int b){
long long carry; // 64-bit
long long temp; // 64-bit
while (b != 0) {
carry = a & b;
a = a ^ b;
temp = ((carry) << 1);
b = (int) temp;
}
return a;
}
```
:::danger
Runtime Error
Line 7: Char 25: runtime error: left shift of negative value -2147483648 (solution.c)
Last executed input
-1
1
:::
-2147483648
= 10000000000000000000000000000000
### try 6
A more compact version of try 4.
```cpp=
int getSum(int a, int b){
int carry; // 64-bit
while (b != 0) {
carry = a & b;
a = a ^ b;
b = ((carry & 0xffffffff) << 1);
}
return a;
}
```
Still `& 0xffffffff` is required, or it will fail by
> Line 6: Char 23: runtime error: left shift of 1073741824 by 1 places cannot be represented in type 'int' (solution.c)
Last executed input
-1
1
Sign in with Wallet
Connect another wallet