python - bit-wise operation unary ~ (invert)

Question

I'm a little confused by the ~ operator. Code goes below:

a = 1
~a  #-2
b = 15
~b  #-16

How does ~ do work?

I thought, ~a would be something like:

0001 = a
1110 = ~a 

why not?

Answer 1

You are exactly right. It's an artifact of two's complement integer representation.

In 16 bits, 1 is represented as 0000 0000 0000 0001. Inverted, you get 1111 1111 1111 1110, which is -2. Similarly, 15 is 0000 0000 0000 1111. Inverted, you get 1111 1111 1111 0000, which is -16.

In general, ~n = -n - 1

Answer 2

The '~' operator is defined as: "The bit-wise inversion of x is defined as -(x+1). It only applies to integral numbers."Python Doc - 5.5

The important part of this sentence is that this is related to 'integral numbers' (also called integers). Your example represents a 4 bit number.

'0001' = 1 

The integer range of a 4 bit number is '-8..0..7'. On the other hand you could use 'unsigned integers', that do not include negative number and the range for your 4 bit number would be '0..15'.

Since Python operates on integers the behavior you described is expected. Integers are represented using two's complement. In case of a 4 bit number this looks like the following.

 7 = '0111'
 0 = '0000'
-1 = '1111'
-8 = '1000'

Python uses 32bit for integer representation in case you have a 32-bit OS. You can check the largest integer with:

sys.maxint # (2^31)-1 for my system

In case you would like an unsigned integer returned for you 4 bit number you have to mask.

'0001' = a   # unsigned '1' / integer '1'
'1110' = ~a  # unsigned '14' / integer -2

(~a & 0xF) # returns 14

If you want to get an unsigned 8 bit number range (0..255) instead just use:

(~a & 0xFF) # returns 254

Answer 3

It looks like I found simpler solution that does what is desired:

uint8: x ^ 0xFF
uint16: x ^ 0xFFFF
uint32: x ^ 0xFFFFFFFF
uint64: x ^ 0xFFFFFFFFFFFFFFFF

Answer 4

You could also use unsigned ints (for example from the numpy package) to achieve the expected behaviour.

>>> import numpy as np
>>> bin( ~ np.uint8(1))
'0b11111110'

Answer 5

Python's unary inversion operator ~x = -(x+1), and this is the same as flipping each bit in memory:

eg

>>> 0b110    # an integer defined with a binary literal
# 0|1,1,0    = in sign|magnitude form
# +|4,2,0    = each bit's contribution to the int
# +1*(4+2+0) =>
6            

>>> bin(~0b110) # get the binary representation of inverted 0b110
# 1|001         = each bit simply inverted (invert sign bit too)
# -|4+2+0 +1    = each bit's contribution to the int, ‡See note
# -1*(4+2+0+1)  = -7    (the answer we want that represents each bit flipped)
# -0b111        = binary representation of -7
-0b111          = it resembles 1|111 but it in memory it is actually 1|001

-0b111 is 1|001 in memory. You shouldn't interpret a -ve binary number representation as what is stored in memory, unlike with a positive binary number.

‡ Note: Negative numbers in binary count backwards, so each -ve bit position is only counted toward composing the int if it's 0, and you must add -1 to the final result:

# in-memory  = int  (displayed as)
1|11..111    = -1   (-0b1)
1|11..110    = -2   (-0b10)
1|11..101    = -3   (-0b11)
1|11..100    = -4   (-0b100)
# and so on...

Answer 6

The problem is that the number represented by the result of applying ~ is not well defined as it depends on the number of bits used to represent the original value. For instance:

5 = 101
~5 = 010 = 2

5 = 0101
~5 = 1010 = 10

5 = 00101
~5 = 11010 = 26

However, the two's complement of ~5 is the same in all cases:

two_complement(~101) = 2^3 - 2 = 6
two_complement(~0101) = 2^4 - 10 = 6
two_complement(~00101) = 2^5 - 26 = 6

And given that the two's complement is used to represent negative values, it makes sense to consider ~5 as the negative value, -6, of its complement.

So, more formally, to arrive at this result we have:

1. flipped zeros and ones (that's equivalent to taking the ones' complement)
2. taken two's complement
3. applied negative sign

and if x is a n-digit number:

~x = - two_complement(one_complement(x)) = - two_complement(2^n - 1 - x) = - (2^n - (2^n - 1 - x)) = - (x + 1)