371: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThis solution implements the bitwise operation approach to add two intege
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThis solution implements the bitwise operation approach to add two integers without using the + or - operators.\n\nThe algorithm starts by initializing a mask variable to 0xFFFFFFFF which is used to ensure that the result stays within the range of 32-bit integers.\n\nThen, using a while loop, the algorithm applies two bitwise operations on a and b until b becomes 0:\n\n1. (a ^ b) & mask: This operation performs the bitwise exclusive OR (^) operation on a and b and then bitwise ANDs (&) the result with the mask variable to ensure that the result stays within the range of 32-bit integers. The result is then stored in a.\n\n2. ((a & b) << 1) & mask: This operation performs the bitwise AND (&) operation on a and b, then left shifts the result by 1 bit (<< 1), and finally bitwise ANDs (&) the result with the mask variable to ensure that the result stays within the range of 32-bit integers. The result is then stored in b.\n\nThe above two operations are repeated until b becomes 0, at which point the value of a is returned as the sum of the original a and b values.\n\nFinally, the result is checked to ensure that it is within the range of 32-bit signed integers (0x7FFFFFFF or 2147483647 in decimal), and if it is greater than the maximum value, it is inverted and subtracted from the mask variable to get the correct negative value.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def getSum(self, a: int, b: int) -> int:\n        mask = 0xFFFFFFFF\n        \n        while b:\n            a, b = (a ^ b) & mask, ((a & b) << 1) & mask\n        \n        return a if a <= 0x7FFFFFFF else ~(a ^ mask)\n\n```
['Math', 'Bit Manipulation', 'Python', 'Python3']