Python Bitwise Inverse Not Flipping Bits

Question

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

Answer 1

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'))

Answer 2

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.