class Solution(object):
def getSum(self, a, b):
"""
:type a: int
:type b: int
:rtype: int
"""
# 32 bits integer max
MAX = 0x7FFFFFFF
# 32 bits interger min
MIN = 0x80000000
# mask to get last 32 bits
mask = 0xFFFFFFFF
while b != 0:
# ^ get different bits and & gets double 1s, << moves carry
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# if a is negative, get a's 32 bits complement positive first
# then get 32bit positive's Python complement negative
return a if a <= MAX else ~(a ^ mask)
Python solution with no "+*/%", completely bit manipulation guaranteed


@dongxinzhuo Python has more than 32 bits for integers. You can try to run "print 2 ** 31"and Python would shows the exact number correctly, while other languages like Java would not. Java only recognizes 2 ** 31 to 2 ** 31  1.
How does integers presented in Python differ from integers in 32bit e.g. Java?
From what I heard, Python has 64 bits. (Please let me know if I am wrong. )
So 1 in Python would look like 0x0000000000000001, but it looks like 0x00000001 in 32bit format.
1 in Python would look like 0xFFFFFFFFFFFFFFFF, but it looks like 0xFFFFFFFF in 32bit format.It seems that the input given by LC is in 32bit format. Since Python would treat it as positive with 1 on the 32 position, we have to use mask to treat it as negative.

Cloud you mind to explain how '' ~(a ^ mask) '' works?
For example, a = 32, b = 32, if we don't handle the negative situation, we will get the result: 4294967232. If we convert the number to binary, it seems the complement of 64 in 32bit integer based. So how the '' ~(a^mask)'' make the 4294967232 to 64, what is principle?

@leeprimer For example, if a is 2 after the loop, a would be 0x00000000FFFFFFFE. What ^mask does here is get a's 32bit complement, so a^mask = 0x0000000000000001. FYI, this is exactly what ~ in Java would do, 2 in Java is 0xFFFFFFFE, its 32bit complement is 0x00000001 in Java. Since the output needs to be in 64bit to be check by OJ, we want 64bit 2. ~ in Python would convert 0x0000000000000001 to 0xFFFFFFFFFFFFFFFE, which is 2 in Python.
In sum, you can consider a^mask gets a's 32bit positive complement with more 32bit 0's on left, and ~ gets the common Python complement.
Basically, this OJ gives us 32bit integers as input and expects 64bit integers as output.

@ranchenwei Think about what b actually is. It is a carry, so it moves 1s towards higher position in 32 bits. Since it moves 1s towards the highest bit and the highest bit is finite 32, it will surely end.

The mask is completely necessary in Python since according to Python's official doc page:
A left shift by n bits is equivalent to multiplication by pow(2, n). A long integer is returned if the result exceeds the range of plain integers.
And:
Long integers have unlimited precision.

@xela2016 said in Python solution with no "+*/%", completely bit manipulation guaranteed:
Python's official STL page
Python's what?
