Bitwise operators

Python has six operators that work on the bits of whole numbers. Four of them combine two numbers place by place; two of them move bits to other places. Each one is a single fast step for numbers that fit in a machine word, and every method in this station is built from them.

And, or, xor

&, | and ^ look at the two numbers one place at a time. The result bit in each place depends only on the two bits in that place, so there are no carries, unlike in addition:

And gives 1 only where both bits are 1. Or gives 1 where either bit is 1. Exclusive or (xor) gives 1 where the bits differ. Step through each one in the figure.

TRIE-5 introduced xor for the bitwise trie. Three of its facts are used again and again: x ^ x is 0, x ^ 0 is x, and the order does not matter (a ^ b ^ c is the same in any order). So if every value in a list appears twice except one, the xor of the whole list is that one value: each pair cancels out.

These operators also work on Python’s negative numbers, using the endless 1s of lesson 1: -6 & 0xFF is 250. Python’s set uses the same symbols for the same ideas: & is the common part, | is everything in either, and ^ is everything in exactly one. Lesson 5 uses this link to store a whole set in one number.

Not

~x flips every bit. With Python’s endless bits, this always gives -x - 1: ~0 is −1, and ~45 is −46. To flip only the lowest w bits, xor with a mask of w ones instead: x ^ ((1 << w) - 1). For 8 bits that is x ^ 0xFF, so 45 becomes 210.

Shifts

x << k moves every bit k places to the left, and 0s come in at the right. Each bit is now worth 2ᵏ times as much, so x << k equals x · 2ᵏ. x >> k moves every bit k places to the right, and the lowest k bits are lost. It equals x // 2**k: divide by 2ᵏ and round down. For negative numbers it also rounds down, so -7 >> 1 is −4, just like -7 // 2. The fourth version of the figure shows both shifts.

Together with &, shifts read single bits: x >> k & 1 is bit k of x. 1 << k is the number with a single 1 in place k, which is 2ᵏ.

Brackets and cost

Python works out arithmetic before shifts, shifts before &, then ^, then |, and comparisons last. Some results surprise people:

1 << k - 1        # 1 << (k - 1), not (1 << k) - 1
x & mask + 1      # x & (mask + 1)
x & 1 == 0        # (x & 1) == 0 in Python
                  # (in C it means x & (1 == 0))
(1 << k) - 1      # k ones: write the brackets

When in doubt, add brackets. They do not slow the code, and they make the meaning plain to the reader.

Cost. A processor does &, |, ^ and shifts on a 64-bit word in one step. Python stores a whole number as a list of pieces of about 30 bits each, and these operators run a fast loop over the pieces in C. So for a number of B bits each operator costs O(B), about B / 30 machine steps, and for numbers below about a billion it is one step. This matters for huge numbers: a loop that shifts a million-bit number one place at a time does a million shifts, and each shift copies all million bits.

Gray codes

When you count 3 → 4 in binary, three bits change at once: 011 → 100. A sensor that reads a position from several bits may catch some of them changed and some not, and read a number that is far off. A Gray code orders the numbers so that neighbours differ in exactly one bit. The usual one is

So gray(0) to gray(7) are 000 001 011 010 110 111 101 100. Why do neighbours differ in one bit? Bit k of gray(n) is bit k of n xor bit k + 1 of n. Going from n to n + 1, the lowest 0 of n (say in place t) becomes 1, and the 1s below it become 0s; nothing above place t changes. For a place below t, both bit k and bit k + 1 of n flip, so their xor stays the same. At place t, bit t flips but bit t + 1 does not, so that xor changes. Above t nothing changes. So exactly one bit of the Gray code changes: the bit in place t.

Reading a Gray code back. The top bit of n is the top bit of g. Going down, each bit of n is the bit of n just above it xor the bit of g in this place. So bit k of n is the xor of all the bits of g from the top down to place k: a running xor, the same idea as a running total. Done one bit at a time, this costs one shift of the whole number per bit, which is slow for huge numbers (see the cost above). A running xor can also be built from blocks that double in size; BITS-P2 asks you to find how.

Now try BITS-P2, From Gray code.