Bitwise Solution explained
The explanation is taken from cracking the coding interview, which anudeepb28 commented on someone else\'s solution.\n\nOur first Instinct in problems like thes
The explanation is taken from cracking the coding interview, which anudeepb28 commented on someone else\'s solution.\n\nOur first Instinct in problems like these should be that we\'re going to have to work with bits. Why, Because when you take the + sign, what other choice do we have? Plus, that\'s how computers do it!\nOur next thought should be to deeply understand how addition works. We can walk through an addition problem to see if we can understand something new\u2014some pattern\u2014and then see if we can replicate that with code. So let, do just that\u2014let, walk through an addition problem. We\'ll work in base 10 so that it, easier to see.\nTo add 759 + 674, would usually add digit [0] from each number, carry the one, add digit [1] from each number, carry the one, and so on. You could take the same approach in binary: add each digit, and carry the one as necessary.\nCan we make this a little easier? Yes! Imagine I decided to split apart the "addition" and "carry" steps. That is, I do the following:\n\nAdd 759 + 674, but "forget" to carry. I then get 323.\nAdd 759 + 674 but only do the carrying, rather than the addition of each digit. I then get 1110.\nAdd the result of the first two operations (recursively, using the same process described in step 1 and 2): 1110 + 323 = 1433.\nNow, how would we do this in binary?\n\nIf I add two binary numbers together, but forget to carry, the ith bit in the sum will be 0 only if a and b have the same ith bit (both 0 or both 1).This is essentially an XOR.\nIf I add two numbers together but only carry, I will have a 1 in the ith bit of the sum only if bits i - 1 of a and b are both 1s. This is an AND, shifted.\nNow, recurse until there\'s nothing to carry.\n\n```\nclass Solution {\n    public int getSum(int a, int b) {\n        if (b == 0) return a;\n\t\t// a ^ b: sum without carry\n\t\t// (a & b) << 1: carry without sum\n\t\t// stop when carry becomes zero, meaning we have nothing more to add\n        return getSum(a ^ b, (a & b) << 1);\n    }\n\n  \n}\n```
[]