[Java/Python 3] Iterative and recursive codes.
Let us start with two 1-bit binary numbers b1 and b2, and we want to compute their sum by bit manipualtions, without using + or -:\n\n1. b1 ^ b2: sum without ca
Let us start with two `1-bit` binary numbers `b1` and `b2`, and we want to compute their sum by bit manipualtions, without using `+` or `-`:\n\n1. `b1 ^ b2`: sum without carry over.\n2. `b1 & b2`: carry over bit. Hence we need to shift it to the left for `1` bit to put it on the right position. e.g., `b1 = 1, b2 = 1` then `b1 & b2 = 1` and left shift `1` bit to get the corrent result: `10`. Therefore, `(b1 & b2) << 1` is the carry over.\n\nNow we obtain two new numbers: `b1\' = b1 ^ b2, b2\' = (b1 & b2) << 1`. \n\n**If we repeat the above procedure, the carry over `b2\'` will be `0` after shifting left for enough times (at most `31` times, in fact much less than that). When the carry over becomes `0`, we NO longer need to add it to `b1\'`, which is the solution already!**\n\n**The above conclusion is also correct for any two integers, not just two `1-bit` binary numbers.** Based on the conclusion, we can implement the following codes:\n\n----\n\n**Iterative versions:**\n\n```java\n    public int sum(int a, int b) {\n        while (b != 0) {\n            int carryOver = (a & b) << 1;\n            a ^= b; // Now a is the sum without carry over.\n            b = carryOver; // b is the carry over now.\n        }\n        return a;\n    }\n```\n\n----\n\n\n**Note**: Python 3 uses different binary representation from Java or C++, so we need a `mask = 0XFFFFFFFF` to make sure that both the sum and carry over parts are with proper signs. If the result is over the upper bound `0X7FFFFFFF = 2147483647` (so should be less than `0X80000000 = 2147483648`), it is actually a negative number.\n\n```python\n    def sum(self, a: int, b: int) -> int:\n        mask = 0xFFFFFFFF\n        while b != 0:\n            a, b = (a ^ b) & mask, ((a & b) << 1) & mask # sum w/o carry over .vs. carry over.\n        return a if a < 0x80000000 else ~(a ^ mask)\n```\n\n----\n\n**Recursive version**:\n\n```java\n    public int sum(int a, int b) {\n        return b == 0 ? a : sum(a ^ b, (a & b) << 1);\n    }\n```\n\n```python\n    def getSum(self, a: int, b: int) -> int:\n        mask = 0XFFFFFFFF\n        if b == 0:\n            return a if a < 0X80000000 else ~(a ^ mask)        \n        return self.getSum((a ^ b) & mask, ((a & b) << 1) & mask)\n```\n\n\n----\n\nFeel free to ask if you have any questions about the post, and please **upvote** if it is helpful.
[]