Beginner Level Explanation With Code
Now we can not use the + operator, which means it is obvious that we have to use some sort of bit manupulation. But the real question is how? \nThe ans lies wit
Now we can not use the `+` operator, which means it is obvious that we have to use some sort of **bit manupulation**. But the real question is **how?** \nThe ans lies within the procedure of the addition, which I am going to show you below.\n\nfrom binary level, how do we exactly add two numbers, let us see -->\n\n```\n         _\na = 2 = 010\nb = 3 = 011\n------------\nc = 5 = 101\n```\n\nIn the position, where we have a dash above, there we are generating a carry, which will be carried over to the next bit, and added to that next bit. So, the addition pattern goes like - \n\n```\n  0         0         1         1\n+ 0        +1       + 0       + 1\n----      ----      ----      ----\n  0         1         1         0 (with a carry 1)\n```\n\nIs this pattern similar to you? Have you seen this in the XOR table? Let\'s see the XOR table quickly - \n\n```\na b | XOR\n- - | - -\n0 0 | 0\n0 1 | 1\n1 0 | 1\n1 1 | 0\n```\n\nThese are the exact same, hence for addition, we need to use the XOR operator. But what to do with the carry? Hey, **we need to add that carry to the next bit**, right? That is what we have seen in the implementation of the addition as well. We will do that only, but we can NOT use addition anyway.\nBut, before that, let\'s do the **XOR** for `2` and `3` example.\n\n```\n-- Doing only XOR --\na = 2 = 010\nb = 3 = 011\n------------\nc = 1 = 001\n```\n\n`1` is NOT our answer, and in this procedure, we have left the carry out, which is `100`. Now what\'s the pattern for finding the carry? It is after we AND the two numbers, we will LEFT-SHIFT the result by 1. Didn\'t get it?\n\n```\n-- Doing only AND --\na = 2 = 010\nb = 3 = 011\n------------\nc = 2 = 010\n-----------\nDoing Left-Shift by 1 (<<1)\n-----------\nc = 4 = 100\n```\n\nSo, we found out the carry as well, and believe me or not, but it is the entire Algorithm. You have to repeat the steps of **1. XOR** and **2. AND with Left-Shift**, until the step no 2. becomes 0, and you will have your answer.\n\nExample - \n\n```\na = 2 = 010\nb = 3 = 011\n-----------\nx = 1 = 001 = a\nc = 4 = 100 = b\n-----------\nx = 5 = 101\nc = 0 = 000\n\nx = XOR & c = AND with Left-Shift\n```\n\nSince carry becomes 0, hence our answer is the XOR result = 5.\n\nBelow is the working code for the same, and you can run this code to find the desired answer.\n\n```\nclass Solution {\n    public int getSum(int a, int b) {\n        while(b != 0){\n            int temp = (a&b)<<1;\n            a = a ^ b;\n            b = temp;\n        }\n        return a;\n    }\n}\n```\n\n**Time Complexity: O(1)**\n**Space Complexity: O(1)**\n\nTime is O(1), because the max and min bounds are 1000 and -1000 respectively, which means the input will NOT be arbitrarily large, and it will be in the limits, hence the time will be constant.\n\nThe code for `c` and `c++` will be very similar, and `python` will be a little different. If you like this approach, then please give me a thumbs up.\n\n# GitHub\nYou can find the code and the entire explanation [here](https://github.com/ShuvamChatterjee28/Algorithms/tree/main/Sum%20of%20Two%20Integers).\nIf you want see the other problem and their algorithms, then go [here](https://github.com/ShuvamChatterjee28/Algorithms).\n\nThanks & Happy Coding :)
['Java']