4

When using pythons inverse ~, it seems the bits are not flipped as I would expect them to be. I believe the confusion lies in my understanding of how python stores numbers using 2's compliment.

myInt = 5 #101
inverse = ~myInt
print(bin(inverse))

Output: -0b110

Expected: -0b010, or -0b10

Satbir Kira
  • 792
  • 6
  • 21

4 Answers4

3

This is not an issue with the ~ operator, which does what it is supposed to, but rather, with the bin function you're using to display the results.

In Python, as in most computer systems, negative integers are stored internally in a "two's complement" binary representation. This means that -1 is represented by a sequence of all 1 bits, and each lower integer modifies that value by the normal integer subtraction rules. So -2 is formed by subtracting 1 from -1 and you get a bunch of 1 bits, followed by a zero as the last bit.

Here are some numbers and their two's complement binary representations in 4-bits:

 0 : 0000
 1 : 0001
 2 : 0010
 5 : 0101
-1 : 1111  # this is ~0
-2 : 1110  # this is ~1
-3 : 1101  # this is ~2
-6 : 1010  # this is ~5

Unlike many other languages, Python's integers don't have a pre-defined bit-length. They're not 16- or 32-bits long, like short and long integers are in C. Rather they're dynamically sized, with more bits being added on as needed to represent larger and larger numbers. This causes a tricky situation when you need to represent the binary digits as text (as the bin function does). If you knew your number uses only 16-bits, you could write out an 16 digits string every time, but a dynamically sized number needs a different solution.

And indeed, Python does something different in the bin function. Positive numbers are written with the shortest number of bits necessary to represent their value. And negative numbers are not written in two's complement (the way they're actually encoded internally), but instead by putting a minus-sign in front of the bit-representation of their absolute value.

So you get a table like this, where the bitwise complements are not obvious:

 0 :    0b0
 1 :    0b1
 2 :   0b10
 5 :  0b101
-1 :   -0b1
-2 :  -0b10
-3 :  -0b11
-6 : -0b110

As for how to get binary representations for negative numbers like the ones in the first table, the only good way is to pick some power of two that is larger than any of your numbers, and add it to all the negative values before formatting:

MY_MAXINT = 2**4
for v in [0,1,2,5,-1,-2,-3,-6]:
    if v < 0:
        v += MY_MAXINT
    print(format(v, '04b'))
Blckknght
  • 100,903
  • 11
  • 120
  • 169
  • I'm disappointed with bin() for negative numbers. On top of that, you can't do bitwise operations on it. Thank you. – Satbir Kira Apr 15 '20 at 02:53
1

This has to do with the way two's complement works for encoding negative numbers. The negative representation of any integer is calculated by inverting the digits and adding one.

If you flip that logic around, inverting a binary representation will negate the value and subtract one. So the inverse of 5 should, indeed, be -6.

~5                                                                                                                                                                                                                                  
# -6

Since Python does not use a fixed number of bits for each integer, there is no way to show all the leading zeros (there are an infinite number). So instead there is the negative sign in front, -0b110 for -6.

Pick any fixed number of bits and you can write the binary number without the negative. For example with 8 bits (one byte), it would be 1111 1010 which is the inverse you expected.

mcskinner
  • 2,620
  • 1
  • 11
  • 21
0

Since Python has signed integers of arbitrary size, conceptually they are sign-extended out to infinity. When we invert the bits 0b101, we do get 0b010, but the sign-extension is also flipped: the number starts with an infinity of 1s rather than 0s. And this 1111111....1010 value is equal to -6, not to -2 - because an all-ones value would be -1, and then we take away the 4 and 1 bits.

In general, ~x for a Python integer is equal to -x - 1 (equivalently, -(x+1)). This is rarely a useful operation for Python code, but you never know :)

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
0

You're right - this behavior does have to do with how Python stores negative numbers in twos-complement. Behind the scenes, negating a number appending an (effectively) infinite list of leading ones to the binary representation. Therefore, while bin(6) is 0b110, bin(-6) is actually 0b010 (you can see this by observing that bin(-6 & 7) = 0b010.

This means that using ~ does two things; it flips the first bit of the binary representation and then flips all the bits again.

sudo-rushil
  • 11
  • 2