Understanding the mask in a Python solution


  • 4
    F

    Still couldn't understand how (a ^ b) & mask works. Why neither C++ nor Java needs this?


  • 0
    C

    Quote from https://wiki.python.org/moin/BitwiseOperators

    Two's Complement binary for Negative Integers:

    Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from "00000000" to "01111111" as the whole numbers from 0 to 127, and reserve "1xxxxxxx" for writing negative numbers. A negative number, -x, is written using the bit pattern for (x-1) with all of the bits complemented (switched from 1 to 0 or 0 to 1). So -1 is complement(1 - 1) = complement(0) = "11111111", and -10 is complement(10 - 1) = complement(9) = complement("00001001") = "11110110". This means that negative numbers go all the way down to -128 ("10000000").

    Of course, Python doesn't use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written "...1111111111111111111011".

    Since there are infinite leading 1 bits for negative integers, the operands in recursive calls getSum(-1, 1) of python will be:

    • 1 -1
    • 2 -2
    • 4 -4
      ... forever

    On the other hand, other language like C and java, 32-bit signed integer will ends with
    ...

    • 1073741824 -1073741824 (0x40000000 0xc0000000)
    • -2147483648 -2147483648 (0x80000000 0x80000000)
    • 0 0

    That is why we need to mask integers in python.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.