Simple Bit-Wise Approach Java (similar to Half-Adder), faster than 100%
The approach is some what similar to the one used in Half-Adder Circuits. We know that sum of two binary numbers is given by a ^ b and the carry is given by a &
The approach is some what similar to the one used in Half-Adder Circuits. We know that sum of two binary numbers is given by ```a ^ b``` and the carry is given by ```a & b```. So if we want to get the actual sum after adding the two numbers, it would be ```sum + carry << 1```.\n\n> **Why?** Let\'s take one case (this is for example, you may verify with more cases) of Half-Adder where ```a = 1``` and ```b = 1```, both in binary. So there sum and carry would be :\n> ```sum = a ^ b = 1 ^ 1 = 0```\n> ```carry = a & b = 1 & 1 = 1```\n> But the actual sum of ```1 + 1 = 10 (2, in decimal)```, which would be ```sum + (carry << 1)    =    0 + (1 << 1)    =    0 + 10    =    10```\n> Also **Why Left-Shift the carry before adding?** Because that\'s what we would do if we would be adding by traditional method, if we add the bit\'s at any given position, we put the carry to the next left position, so the Left Shifiting sures that the carry of the current bit is added to the next left bit.\n> \nBut wait, we can\'t use ```+```, so how  would we do ```sum + carry << 1``` ? \n\nThe answer is, here we can se our good old recursion coming into play. Won\'t the question be same if ```sum``` would be our new ```a``` and ```carry << 1``` would be our new ```b``` ? Yes, that\'s it. Then what would be the base case? The base case would be when our ```carry == 0```, because then what our ```sum``` contains would be our actual sum.\n\nBelow is the Java Code for the above algorithm \uD83D\uDC47\n\n```java\nclass Solution {\n    public int getSum(int a, int b) {\n        int sum = a ^ b, carry = a & b;\n        while(carry != 0) {\n            a = sum;\n            b = carry << 1;\n            sum = a ^ b;\n            carry = a & b;\n        }\n        return sum;\n    }\n}\n```
['Bit Manipulation', 'Java']