Bitwise xor 0xFFFFFFFF?

0

I couldn't wrap my head around this:

def expr(a):
    return ~(a ^ 0xFFFFFFFF), a ^ 0xFFFFFFFF, ~a, a

print(expr(0xFFFFFFFF))
print(expr(1))
print(expr(0))  
print(expr(-1))

I understand ~a means two's complement of a, but a ^ 0xFFFFFFFF also flips all the bits, but python will interpret it as a large number. I know Python3 is using unbound integer size, how does that work? Can someone ELI5 (Explain Like I'm Five)?

Results:

(         -1,           0, -4294967296, 4294967295)
(-4294967295,  4294967294,          -2,          1)
(-4294967296,  4294967295,          -1,          0)
( 4294967295, -4294967296,           0,         -1)

UPDATE: I guess my question can be reduced to this: in C, 111...1 can represent -1, I got this, because it's 32 bits. In Python, the integer size is unlimited, how do you represent -1 in binary? 111...1 is a large positive integer, no?

python-3.x
bit-manipulation
xor
twos-complement
asked on Stack Overflow Mar 16, 2018 by (unknown user) • edited Jul 29, 2018 by martineau

2 Answers

2

In Python, the integer size is unlimited, how do you represent -1 in binary? 111...1 is a large positive integer, no?

Positive numbers have an infinite sequence of leading zeros. That is, if we need to represent the number 100101 (equal to 37), that's equal to ...000100101, with as many zeros as you like in front. No computer system tries to store all of those leading zeros, because there are infinitely many, but some leading zeros might get stored in order to pad the number out to a "reasonable" size, such as 32 or 64 bits.

Python extends this concept to negative numbers by saying that they have an infinite number of leading ones. So if you need to represent -37, that would be ...111011011, with as many ones as you need in front. Similarly, -1 is just ...1111. So if you XOR -1 with another Python integer, it will flip all of that number's bits, including its leading zeros or ones (as if you had used the tilde operator). Unfortunately, Python does not have a convenient binary notation for "infinite leading ones," so you cannot write (for instance) 0b...111 as an integer literal; you must use -1 instead, or invert it and write ~0b0.

While this may sound ridiculous, it is actually quite mathematically sound. Under the 2-adic numbers, these sequences with infinite leading ones are formally equivalent to the corresponding negative integers. If you prefer an approach more grounded in computer engineering, you might imagine that the Python integers automatically sign-extend to however wide they need to be (which is more or less the actual implementation).

answered on Stack Overflow Mar 17, 2018 by Kevin
1

0xFFFFFFFF is a large number; it's the hexadecimal representation of 232-1. Python's ints are represented internally as a linked list of C longs, allowing theoretically unbounded size. Bitwise XOR (^) in Python uses zero values for the bits more significant than those you've given, so the net result is that only the lower 32 bits are flipped, resulting in behavior that diverges from what you get in C, where there are only 32 bits and the net result is that 'all' the bits are flipped.

answered on Stack Overflow Mar 17, 2018 by Temsia Carrolla • edited May 25, 2020 by Wolf

User contributions licensed under CC BY-SA 3.0