bit-wise operation unary ~ (invert)

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?

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

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

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

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

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'

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)