java recursive with explanation
code: \n\nclass Solution {\n    public int getSum(int a, int b) {\n        int carry = (a&b)<<1;\n        int sum = a^b;\n        if(carry == 0)\n            re
code: \n```\nclass Solution {\n    public int getSum(int a, int b) {\n        int carry = (a&b)<<1;\n        int sum = a^b;\n        if(carry == 0)\n            return sum;\n        return getSum(carry,sum);\n    }\n}\n```\n\nexplanation: \nfor every addition, you have to add the sum and the carry. \n\ndecimal ex. \n2+5 = 7\n\t    = 0(carry)  + 7(sum) \n3+9 = 12\n        = 10 (carry) + 2 (sum (which is 12mod10) )  \n\t\t\nbinary ex. \n10 + 01 = 11\n              = 00(carry) + 11(sum) \n\t\t\t  \n1010 + 1010 = 10100\n                     = 10100(carry) + 0000(sum) \n\nin binary: \nxor operator will give us the sum; (a^b)\nand operator followed by left shift of 1 bit will give us the carry; (a&b)<<1\n\nwe just need to find the sum and carry of the addition and add them recursively, until the carry is 0 (stop case for recursion). This is guaranteed to happen because of the left shift (it creates 0s on the right, preventing future carrys to occur on the right while continually moving to the left, therefore eventually the carrys run out).  \n\n
[]