The action of the bitwise NOT operator is very simple – it inverts all of the bits, setting ones to zeros and zeros to ones:
a
~a
0
1
1
0
Simple though that seems, the way that Python uses bignums to represent bit patterns presents two different problems. The first is, knowing how many leading zeros the input bit pattern has. In other languages bit patterns are always a fixed size – usually 32 or 64 bits. When you use the NOT operator on a bit pattern all of the bits are inverted. So if you write:
a = x0F
b = ~a
and there are 32 bits, the result in b is:
0xFFFFFFF0
You can see that the value stored in a has been treated as if it was:
0x0000000F
In the case of Python, however, with no fixed number of bits there are an arbitrary number of leading zeros and so the result could be:
0x...FFFFFFFFFFFFFFFFFFFFFFFFFFF0
where the … means as many bits as available memory allows.
To avoid this Python only uses as many bits as necessary to represent the value and a single leading zero as the sign bit. As in the case of a general bitwise operation, the sign bit is extended to match the largest of the bit patterns involved.
What this means is that:
a = 0x0F
print(~a )
displays a result of -16. The reason is that the bit pattern stored in a is 1111 which is converted to 0 1111 with the sign bit of zero signifying a positive number. Next the bits, including the sign bit, are inverted to give 1 0000 which is -16 in two's complement form. If you try to print this in binary then you get the result:
-0b10000
which is probably not what you are expecting but, due to the conversion to two's complement, does give you the bit pattern you expect if you make use of it. That is, -0b10000 behaves like 0b0, apart from the sign bit which you can usually ignore. Each time the value in a bignum is converted to two’s complement and then back to signed magnitude representation. So, as long as you don’t examine the value in the bignum, everything works as if you were working with a two's complement bit pattern.
Included in the chapter but not in this extract
Masks
Using Masks
Shifting Values
Testing a Bit
Bit Manipulation and Arithmetic
Bit Manipulation As Art
Summary
The fundamental data entity is the bit pattern and it is up to the program and programmer to assign a meaning to any particular bit pattern.
Hexadecimal (hex) makes specifying a bit pattern easier as each hex symbol corresponds to four binary bits.
Number bases that are a power of 2 have the property that they are easier to convert to binary. The other base that is useful is octal which specifies three bits per symbol.
The fact that Python uses unlimited precision integers, bignums, makes working with bit patterns different to the usually encountered fixed width bit patterns which are typically 16, 32 or 64 bits in size.
The bitwise operators &, |, ^, ~ perform logical operations on pairs of bits.
Negative numbers are a problem for bitwise operations because bignums are stored in sign-value representation and bitwise operations generally use two's complement representation.
You cannot create a negative bignum using a binary value because you cannot set the sign bit. The only way is to use a negative sign.
The not ~ operator is particularly difficult to understand unless you think of it as creating additional sign bits that are then trimmed back to a single sign bit.
It is helpful to think in terms of masks to set and unset particular bits in a bit pattern.
You can use a mask approach to testing if particular bits in a pattern are a zero or a one.
The shift operators << and >> shift the bit pattern to the left and right. Left shifts move zeros into the left and right shift moves a copy of the sign bit into the most significant bit.
An alternative to using logical bitwise operations is to use arithmetic. This is usually harder to understand, but it has the advantage of working in other number bases.
Bit manipulation is an art form and you can spend many hours trying to find a clever and efficient way of doing any task.
