5

I am looking at solutions for this question:

Given two integers a and b, return the sum of the two integers without using the operators + and -. (Input Limits: -1000 <= a, b <= 1000)

In all these solutions, I am struggling to understand why the solutions do ~(a ^ mask) when a exceeds 32-bit number max 0x7fffffff when evaluating a + b [see code below].

def getSum(self, a: int, b: int) -> int:
    
    # 32bit mask
    mask = 0xFFFFFFFF # 8Fs = all 1s for 32 bits

    while True: 
        # Handle addition and carry 
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        if b == 0:
            break

    max_int = 0x7FFFFFFF

    print("A:", a)
    print("Bin A:", bin(a))
    print("Bin M:", bin(mask))
    print("  A^M:", bin(a ^ mask))
    print("~ A^M:", bin(~(a ^ mask)))
    print("  ~ A:", bin(~a))

    return a if a < max_int else ~(a ^ mask)

I don't get why we need to mask a again when returning answer?

When exiting the loop it was already masked: a = (a ^ b) & mask. So why can't we just do ~a if the 32nd bit is set to 1 for a?

I looked at The meaning of Bit-wise NOT in Python, to understand ~ operation, but did not get it.

Output for a = -12, b = -8. Correctly returns -20:

A: 4294967276
Bin A: 0b11111111111111111111111111101100
Bin M: 0b11111111111111111111111111111111
  A^M: 0b10011
~ A^M: -0b10100
  ~ A: -0b11111111111111111111111111101101
Improve this question
16
  • @TimRoberts do you say a is an unsigned value because we do mask at each iteration which drops the sign bit? Since it will be one of the infinite 1s? Commented Feb 18, 2023 at 20:44
  • Or a.__add__(b). Commented Feb 19, 2023 at 0:09
  • Or math.log(math.exp(a) * math.exp(b)). Commented Feb 19, 2023 at 0:16
  • 1
    I know there are some other options, but I want to use this question as a vehicle to understand bitwise operations and how the adder works a little better. Commented Feb 19, 2023 at 0:45
  • a is technically not unsigned. All integers in Python are signed, but it is a positive value because you never do anything to make it negative. If you are working in a language with 32-bit integers, then setting bit 31 makes it negative. That doesn't happen in Python. I can add as many bits as I want, and it will stay a positive number. We can't SEE the sign bit, we can't SET the sign bit. Commented Feb 19, 2023 at 4:54

2 Answers 2

Reset to default
2

You forgot to specify constraints of the original problem, that the a and b are in [-1000, 1000]. That code is a port of a C or Java implementation, which assumes a and b are 4 byte signed integers. And I'm not sure you understand the (a ^ b) and (a & b) << 1 code correctly. The former adds i-th bit of the a and b ignoring a carry bit for every bit. The latter gets all that ignored carry bits.

To the main point, the last operation ~(a ^ mask) is for dealing with a negative integer. The a ^ mask inverts the lower 32 bits of the a and preserves the other upper bits. So, the bitwise NOT of the result, ~(a ^ mask) preserves the lower 32 bits of the a and inverts the other upper bits. Because the upper bits(other than the lower 32 bits) of the a are all zero, the ~(a ^ mask) is just setting all the upper bits to one. It's equivalent to a | ~mask, which is much more readable.

See the following example.

print(~(0xffffffff ^ 0xffffffff)) # This will output -1.
print(~(0xfffffffe ^ 0xffffffff)) # This will output -2.
print(~0xffffffff) # This will output -4294967296(-0x100000000).
Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

But a was already 32 bits long (we do a & mask). So ^ is just flipping the bits right? Also as a whole is it calculating 2's compliment?
also, why is a | ~mask more readable?
Yes, you are right for the first question, since the upper bits(other than the lower 32 bits) of a ^ mask are all zero. And for the second question, by "as a whole", you mean the ~(a ^ mask)? Then no it's not calculating a two's complement. It converts a positive Python integer representing a negative integer as a two's complement(32bit signed integer) into a negative Python integer. And finally, the a | ~mask is more readable if you think all the variables represented as lists of bits.
So do you mean a ^ mask gives a 2s complement? And then ~(a^ mask), converts 2s complement to signed number? How/Why exactly does that work? Qualitatively I kind of get that ~ will flip all remaining 0s after the first 32 bits to 1 (and give us back the first 32 bits since we XORed them before). But does that also flip the sign bit so Python now knows this is a negative number?
If possible could you show me an example of writing out 1s (say for 8bits) of how this work? Or is there any place I can read this with examples that write out numbers in 1s and 0s and show the working? I still do not get why a | ~mask is more readable (someone else mentioned this in a comment on leet code too)
|
0

Here's a helpful link - Differentiating a 2's complement negative number and the corresponding positive number.

Because of the bounds, we will never have a positive number overflow. (numbers are only between [-1000, 1000]). So we know that when the 32nd bit was set it was because it was a negative number.

Note that if our range allowed positive number addition to overflow too, then there would be no way to distinguish between positive number setting 32nd bit and negative number setting it.

So we do ~(a ^ mask) to retain bits of a till the first 32 bits and add infinite leading 1s to it so Python knows this is a negative number.

If you look at Bin A, it's already the 2s complement representation of -20. But right now Python treats it as a positive number. So we need to tell Python to treat it as a negative number using ~(a ^ mask).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.