#371 Sum of Two Integers

###### 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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.