Python bitwise operators and shifts

Why this matters

Every number inside a computer is stored as a row of bits. The operators in this lesson look at those bits directly, one position at a time. Programmers use them to pack several yes-or-no settings into one number, to speed up work that would otherwise need division, and to solve puzzles that interviewers like to ask. You will see them in hash tables, in graphics code, in network addresses and in compression. Many of the tricks are short enough to remember and strange enough to impress.

This lesson is the last of the operator lessons, and it asks the most of your imagination. Take your time with the first two sections. Once you can read a number as a row of bits, every trick in the rest of the lesson follows from one or two rules.

Python differs from many languages here in two ways. A Python int has no fixed width, so ~5 and -8 >> 1 follow the rules of an endless row of bits. Python also has no unsigned right shift. Both points are shown below.

Start from the first principle: a number is a row of bits

A bit is one binary digit. It is either 0 or 1. Binary is the base-2 counting system. In decimal, each column is worth ten times the column to its right. In binary, each column is worth twice the column to its right. The columns, from right to left, are worth 1, 2, 4, 8, 16, 32, and so on.

Here is how the first eight numbers look when written in binary:

So 5 is 101 in binary: a four, no two, and a one. Python can show the binary form of any number with bin, and format can pad it to a fixed width. The function format(5, "08b") gives 00000101.

Think of a row of light switches on a wall. Each switch is either on (1) or off (0). A number is one pattern of switches. A bitwise operator compares two rows of switches column by column. It does not carry or borrow between columns, the way addition does. Each column is handled on its own, and the result is a new row of switches.

Because the columns are independent, bitwise operators are very fast. The processor can handle many columns in one step.

Two's complement: how negative numbers are stored

Before the operators, you need one more fact. Python shows negative numbers with a minus sign, but the bit operators work on negative numbers as if they were stored with the scheme called two's complement. The idea is simple. To get the negative of a number, flip every bit and add 1. Take 5, which is 00000101. Flip every bit to get 11111010, then add 1 to get 11111011. That is -5 in an 8-bit example.

A useful shortcut is that flipping every bit of n gives -n - 1. So ~5 is -6, which is the same as -5 - 1. The leading bit of a negative number is 1. You do not need to convert negative numbers by hand, but you must know that a negative number has a leading 1 bit. That is why right shifts behave differently for negative values, as you will see below.

The bitwise operators

There are four bitwise operators. Each one compares bits in the same column.

Here is a complete program that prints each operation, with a helper that writes out the eight low bits of a result:

The output is:

a     = 00000101 (5)
b     = 00000011 (3)
a & b = 00000001 (1)
a | b = 00000111 (7)
a ^ b = 00000110 (6)
~a    = 11111010 (-6)

The bits helper uses format with the pattern 08b. The b means binary, and 08 means eight digits, padded with zeros on the left. The expression n & 0xFF keeps only the lowest eight bits, which is why ~5 shows as 11111010. The number 0xFF is 11111111 in binary, so ANDing with it keeps the last eight columns and clears the rest. The printed decimal, -6, shows the whole value.

Check the table column by column. In the AND row, only the rightmost column has 1 in both 101 and 011, so the result is 001. In the OR row, every column has a 1 in at least one input, so the result is 111. In the XOR row, the left column is 1 and 0, which differ and give 1. The middle column is 0 and 1, which differ and give 1. The right column is 1 and 1, which are the same and give 0. That makes 110.

Shifts: moving the bits

A shift moves every bit a number of places to the left or to the right. Python has two shift operators, and one more form that other languages have is not in Python.

• x << k moves the bits k places to the left. Zeros fill the empty columns on the right. Each place doubles the value, so x << k is x * 2**k.
• x >> k moves the bits k places to the right. The bits on the right fall off. Each place halves the value and rounds toward negative infinity for negative numbers.
• Python has no >>> operator. For an unsigned right shift, first mask the number to a fixed width, then shift. This is shown below.

The next program shows the shifts on several numbers. Predict each line before you run it, using the rule that each place doubles or halves the value.

The output is:

10
20
5
-4
15
2147483647

The first two lines are doublings. Five doubled is 10, and then doubled again is 20. The third line is a halving: 20 shifted right by two places is 5. The fourth line is the important one. -8 is an endless row of leading 1s followed by 000. Shifting it right by one with >> keeps the sign, so the result stays negative. The answer is -4, which is -8 halved.

The fifth line is the unsigned shift written in Python. The mask 0xFFFFFFFF keeps the lowest 32 bits, so -8 becomes the 32-bit pattern whose top four bits are all 1. Shifting that pattern right by 28 places leaves those four bits as the lowest four, 1111, which is 15. The last line does the same for -1, and the result is the largest positive 32-bit value, 2147483647.

For non-negative numbers, >> gives the same result as an unsigned shift. The difference only shows for negative numbers. Remember it, because it matters whenever a negative number is shifted.

Hexadecimal and binary literals

A row of 32 zeros and ones is hard to read at a glance. Programmers group the bits in fours, because four bits can make 16 different patterns. Each group is written as one hexadecimal digit, which is base 16. Hexadecimal uses the digits 0 to 9, then the letters A to F for the values 10 to 15.

The table shows the first sixteen values in binary and hexadecimal:

In Python, a hexadecimal literal starts with 0x, and a binary literal starts with 0b. So 0xFF is 255, which is 11111111 in binary, and 0b101 is 5. Python also allows underscores inside a literal to make groups easy to see, as in 0b1010_1010, which is 170.

The output is:

255 5 170 3832789
11111111 0x30

Hex is especially useful for masks. The value 0xFF keeps the lowest eight bits. The value 0xF0 keeps the highest four bits of a byte (eight bits). Check an AND with two masks. 0xF0 & 0x3C is 11110000 & 00111100, which is 00110000, which is 0x30. Reading the result in hex takes one step, where the binary form takes eight digits.

You do not need to be fast with hex to use this lesson. You do need to read it, because error messages, memory dumps and colour codes all use it.

Reading one bit: a worked trace

The rule (n >> i) & 1 reads bit i of n. The steps are easiest to see on a table. Use n = 12, which is 1100, and check bits 0 to 3, one at a time.

The shift moves the wanted bit into the rightmost column, and the AND with 1 throws away every other column. Row 3 is the one to study. 12 >> 3 is 1, because the bit at position 3 is the only one left. Its AND with 1 is 1, so bit 3 is set. Notice that the shift can make the number smaller than the bit you are reading, but the rule still works, because only the last column matters after the AND.

Packing settings: a traced example

Here is a whole sequence of flag operations, traced with the bits written out. The next section gives the four mask jobs in full, and this example uses all of them. Three settings are stored in one number: READ is 1, WRITE is 2 and EXEC is 4. Each setting is a single bit. The table shows the value after each line, in three-column binary.

Line 3 is a test, so it does not change the value. Its answer is False, because the WRITE column is 0. Line 4 toggles READ. READ was 1, so it becomes 0. Line 5 clears EXEC, which was 1, so the value ends as 0. Each line changes exactly the column it names, and nothing else. That is the reason masks are reliable. The other columns are never touched.

The same five lines in Python, with the value printed in binary after each one:

The output is:

1 001
5 101
False 000
4 100
0 000

Try writing the same five lines in your own program and print the value after each one. Then check each printed value against the table. If a line changes a column you did not name, the mask in that line is wrong.

Masks: reading and changing single bits

A mask is a number used with & or | to pick out or change particular bits. Masks are how programs store several yes-or-no settings in one integer. Each setting is one bit, and the mask names which bit to look at.

Here are the four basic jobs. Use a bit position counted from 0 at the right.

• Read a bit. (n >> i) & 1 moves bit i to the rightmost column and keeps only that column. The result is 0 or 1.
• Set a bit to 1. n | (1 << i) ORs in a 1 at position i. A 1 in the mask forces that column to 1, and every other column is unchanged.
• Clear a bit to 0. n & ~(1 << i) ANDs with a mask that has a 0 at position i and 1s everywhere else. The column becomes 0, and the rest are unchanged.
• Toggle a bit. n ^ (1 << i) XORs the column, so a 0 becomes 1 and a 1 becomes 0.

Check the reading rule with a short example. The number 12 is 1100. Bit 2 is the third column from the right, and it is 1. The shift 12 >> 2 is 11, and 11 & 1 is 1. So bit 2 of 12 is set. This is why the expression (n >> i) & 1 returns the bit.

Permissions in a file system work the same way. Read might be bit 0, write bit 1 and execute bit 2. A file with read and execute has the mask 101, which is 5. Checking for write means (perms & 2) != 0. Setting execute means perms | 4. The whole permission set fits in one number, and each check is one fast operation.

Python's & binds tighter than its comparison operators, so n & 1 == 1 means (n & 1) == 1. Other languages, such as Java, rank == above &, so the same text means n & (1 == 1) there. Write the brackets anyway, because they say what you mean in every language.

Classic tricks

Interviewers like bitwise questions, because the answers are short and the reasoning is elegant. Here are the most common ones, with an explanation of why each works.

Odd or even. The last bit of an odd number is always 1. So (n & 1) == 1 tests for an odd number, and it also works for negatives, because two's complement keeps the last bit the same. The arithmetic lesson gave the test n % 2 != 0. Both are correct, and the bit test is the form interviewers expect.

Power of two. A power of two has exactly one bit set. Subtracting 1 flips that bit to 0 and turns every column below it into 1. So the AND of n and n - 1 is 0, and that happens only for powers of two. Exclude zero, because 0 & -1 is 0 and the test would accept it.

The program below shows the test on six inputs. It is a complete program with one function, so you can see each answer:

The output is:

True
False
True
False
True
False

The last line tests -2**31. Its top bits are all 1, so the AND with n - 1 is never zero, and the test gives False even without the n > 0 check. The check is still the clearer rule. In a language with fixed-size integers, the smallest value wraps when you subtract 1, and then the check is what keeps the answer correct. Always check the edge cases of a bit trick.

Counting one bits. Here is a neat trick. The expression n & (n - 1) removes the lowest set bit of n. Each time you apply it, the count of one bits goes down by one. So you can count the one bits by repeating the step until the number reaches 0. This is called Brian Kernighan's method. The repeating part needs a loop, which the loops module explains in full. Python also has the method int.bit_count, which does the same job.

The output is:

1023 has 10 one-bits
10

The number 1023 is ten ones in binary, 1111111111. The loop removes one lowest bit on each pass, so it runs ten times. The loop does one step per set bit, not per column, so for a number with few ones it is very fast. The method is a common interview answer, and it runs in time proportional to the number of one bits.

The lowest set bit. The expression n & -n isolates the lowest one bit. In two's complement, -n flips every bit above the lowest one and leaves the lowest one and the zeros below it unchanged, so the AND keeps only the lowest one. For 12, which is 1100, the answer is 0100, which is 4. Interviewers use this to find the largest power of two that divides a number.

XOR cancels pairs. XOR has two useful properties. x ^ x is 0, and x ^ 0 is x. So if you XOR together a list in which every number appears twice except one, the pairs cancel, and the answer is the one number that is left over. This is the classic "single number" question. The program below XORs five numbers. Four of them are pairs, and one is alone.

The output is:

alone: 9

The number 4 cancels with 4, and 7 cancels with 7. What remains is 9. The program does not need to know which number is alone, or where it sits in the list. The answer comes out of the algebra of XOR. The program uses one name, result, and one augmented operator for each number. That is the same accumulate pattern you saw in the assignment lesson, with XOR in place of addition.

The standard library can also do the whole fold in one line with functools.reduce and operator.xor, but the loop shows each step.

Binary search and the midpoint

Binary search finds a value in a sorted range by cutting the range in half at each step. It needs the middle index, which is lo + (hi - lo) // 2 for the current range from lo to hi. Each comparison moves the middle to the centre of the remaining range.

The formula for the middle is written as lo + (hi - lo) // 2, not (lo + hi) // 2. In Java and C the reason is overflow. The sum lo + hi can pass the limit of a 32-bit int, and then it wraps to a negative number. Python integers do not wrap, so (lo + hi) // 2 is correct in Python. The next program shows the sum with Python integers and with a fixed 32-bit type.

The output is:

python mid: 2123500000
python good mid: 2123500000
32-bit sum: -47967296
32-bit mid: -23983648

In Python both forms give 2123500000. The sum lo + hi is 4247000000, which does not fit in 32 bits. The ctypes.c_int32 type wraps it to -47967296, and dividing that by 2 gives a negative middle index. This is the bug that the subtraction form avoids in languages with fixed-size integers. In Python, use lo + (hi - lo) // 2 when the code may be ported to a fixed-size language, because it is safe in both.

The standard library module bisect already does binary search for sorted lists, so you rarely write the midpoint by hand in Python. The module is documented in the Python standard library reference.

Bits in real systems: a colour value

A common real use of shifts and masks is a colour. Web and graphics code often stores a colour as one 24-bit number, written in hex as 0xRRGGBB. The first two hex digits hold the amount of red, the next two hold green, and the last two hold blue. Each part runs from 0 to 255, which fits in eight bits.

Take the colour 0x3A7BD5. To read the red part, shift right by 16 places to bring the top eight bits down to the lowest eight columns, then keep only those columns with a mask. The steps are:

• Red: (color >> 16) & 0xFF. The shift leaves 0x3A, and the mask keeps it. The answer is 58.
• Green: (color >> 8) & 0xFF. The shift leaves 0x3A7B, and the mask keeps the low byte, 0x7B. The answer is 123.
• Blue: color & 0xFF. No shift is needed, because blue is already in the lowest eight columns. The answer is 213.

The output is:

58 123 213
0x3a7bd5

To put the parts back together, run the steps in reverse. Shift red left by 16, shift green left by 8, and OR the three results with blue. The OR is safe here because the three parts occupy separate columns, so no column is set twice. Python prints the hex digits in lower case, so 0x3a7bd5 is the same value as 0x3A7BD5.

The same pattern appears in many places. A packed date, a network address, a file's flags and a pixel in an image all store several small numbers in one integer. The rule is always the same. Shifts move each part into place, and masks cut each part out. Once you can read one part, you can read them all.

Common mistakes and the messages you will see

Bitwise code has some sharp edges. Some mistakes give an error, and others give a number that looks plausible.

Mistake 1: & on a value and a comparison

In Java, == ranks above &, so n & 1 == 1 is an error there. Python ranks & above the comparison operators, so the line works. The safe habit is still to write the brackets, because a reader from another language will read the line differently:

The output is:

True
True

Mistake 2: a shift count that is negative

Python does not wrap a shift count. A shift by 40 gives the mathematically correct result, and a negative shift count is an error:

The output is:

1099511627776
8589934592
Traceback (most recent call last):
  File "/path/to/main.py", line 3, in <module>
    print(1 << -1)
          ~~^^~~~
ValueError: negative shift count

Java masks the shift count to the width of the type, so a shift of 40 on an int becomes a shift of 8. In Python the count is not masked, so the first two lines show the true values. Keep the count non-negative, and remember that the value grows without limit.

Mistake 3: & and and mixed up

With bools, & gives the same answer as and, but it does not short-circuit, as the previous lesson explained. With integers, & is the bit operator, so 5 and 3 gives 3, which is not a bit result. Check which one you need: bits use &, decisions use and.

The output is:

1 3

Mistake 4: assuming >> fills with zeros

For a negative number, >> keeps the sign. The line -8 >> 1 prints -4, not a large positive number. Python has no >>> operator. To get the unsigned result for a 32-bit value, mask the number first, as the shifts section showed.

Mistake 5: confusing XOR with OR

5 | 3 is 7, but 5 ^ 3 is 6. In a mask, OR sets bits and XOR toggles them. Using XOR where you meant OR can flip a bit back to 0 if it was already 1. Python accepts both, so check the operator against the job.

Debugging a flag that flips the wrong way

A realistic bug uses a permission mask. A program stores three settings in one number: read is 1, write is 2 and execute is 4. A user should have read and execute, so the value should be 5. The code sets the value like this:

It prints 4. The last line was meant to clear the read bit, but XOR toggles it, and the bit was already on, so it turns off. That is correct for toggling, but the job was clearing. The fix is perms = perms & ~1, which ANDs with a mask that has a zero in the read column. Here the fixed version also prints 4, because the read bit was set and is now cleared. The two lines give the same answer only because read was set. If the read bit had been off, the XOR version would have set it, and the AND version would have left it off. So the line that changes the bit must match the job, or the bug hides until a specific input appears.

The output is:

4 100

The method for finding this kind of bug is to write the value in binary after each line. Use bits from the first program in this lesson. Seeing 00000100 after a line that should have set bit 0 shows the error straight away.

Variations and edge cases

Bit tricks depend on the width of the value, so check the edges.

• Zero. n & (n - 1) is 0 for zero. The power-of-two test needs n > 0 to reject it.
• Negative numbers. Python treats a negative number as an endless row of leading 1 bits. A mask such as & 0xFF shows its low eight bits.
• Fixed sizes. A value that must fit in 32 or 64 bits needs a mask or a fixed-size type such as ctypes.c_int32. The arithmetic lesson covers the wrap-around.
• Shift counts. A shift count must not be negative. A large count gives a large number, not a wrapped one.
• Unsigned data. Python has no unsigned integer type. Use a mask to get the unsigned value, as shown in the shifts section.

Interview-style patterns

Bitwise questions come up in three shapes. Know which shape a question is.

Count or test bits. Use n & (n - 1) to count set bits or to test for a power of two. Explain that each step removes exactly one set bit, so the count is the number of set bits, not the number of columns.

Cancel pairs. XOR a sequence to find the one value that has no partner. Explain the two properties, x ^ x is 0 and x ^ 0 is x, and say that the order of the numbers does not matter, because XOR is commutative (order does not matter) and associative (grouping does not matter).

Pack and unpack flags. Use one bit per setting, with masks to read, set, clear and toggle. Explain that each check costs a single operation, which is why flags are common in systems code.

Packed fields. Some questions ask you to store several small values in one integer, such as a day, a month and a year, and to read them back. The answer is to give each field its own range of columns. Shift the field into place when you write it, and shift and mask it out when you read it. Explain why the fields must not overlap, because an overlap makes an OR silently merge two values.

Each pattern has a cost that is easy to state. Counting set bits takes one step per set bit. Cancelling pairs takes one pass over the sequence. Flag checks take one operation each. A later module explains how to state these costs formally.

A checklist for bit code

Use this list before you trust a bit expression.

• Write the value in binary, column by column, before and after each line.
• Put brackets around every &, | and ^ that sits inside a comparison.
• Mask a negative number to its width with & 0xFF or & 0xFFFFFFFF before you print it as bits.
• Use >> on purpose, and check the sign for negative inputs.
• Test zero, the largest and smallest values, and any value with a single bit set.
• Name each mask with a constant, so the reader sees which bit it is for.

Practice

1. (Easy) Compute 12 & 10, 12 | 10 and 12 ^ 10 by hand in binary, then check them with a program.

Show the answer

12 is 1100 and 10 is 1010. The AND is 1000, which is 8. The OR is 1110, which is 14. The XOR is 0110, which is 6. Check with print(12 & 10, 12 | 10, 12 ^ 10), which prints 8 14 6.

2. (Easy) Multiply a number by 8 using only a shift.

Show the answer

n << 3. Three places to the left doubles the value three times, which multiplies by 2 times 2 times 2, which is 8.

3. (Easy) Write a condition that is True when n is even, using a bit operator.

Show the answer

(n & 1) == 0. The last bit of an even number is 0, so the AND with 1 is 0. The brackets make the intent clear, even though Python would also read n & 1 == 0 correctly.

4. (Medium) Predict the output of print((-1 & 0xFFFFFFFF) >> 28) and print(-1 >> 28).

Show the answer

The first prints 15, and the second prints -1. The mask turns -1 into the 32-bit pattern of all 1s, and the shift by 28 leaves the four top bits, which is 15. The signed shift in Python keeps the sign, so every column stays 1, which is -1.

5. (Medium) Write an expression that sets bit 3 of flags to 1 and leaves the other bits as they were.

Show the answer

flags | (1 << 3). The mask has a single 1 at position 3, so OR forces that column to 1 and leaves every other column unchanged.

6. (Medium) Write an expression that clears bit 3 of flags and leaves the other bits as they were.

Show the answer

flags & ~(1 << 3). The mask 1 << 3 has a 1 at position 3, and its NOT has a 0 there and 1s everywhere else. ANDing keeps every other column and clears column 3.

7. (Medium) Explain what the check n > 0 adds to the test (n & (n - 1)) == 0.

Show the answer

The test alone says yes for 0, because 0 & -1 is 0. The check n > 0 rejects zero. In Python a negative number always has leading 1 bits, so the AND of n and n - 1 stays negative and is never 0. In a fixed-size language, the smallest value wraps when you subtract 1, and then the test can say yes for it, so the check matters there too.

8. (Medium) Predict the output of print(1 << 33).

Show the answer

It prints 8589934592. Python does not wrap the shift count or the result. The value is 2 to the power 33. A fixed 32-bit type would give a different answer.

9. (Hard) Using XOR, write a condition that is True when two integers a and b have different signs. Explain why it works.

Show the answer

(a ^ b) < 0. XOR sets the sign bit of the result only when the two sign bits differ. A negative result means the sign bits differ, which means the signs differ. Zero counts as non-negative here, so the check treats zero as positive.

10. (Hard) A list has every number appearing three times except one, which appears once. Explain why the XOR trick from this lesson does not work for this version, and what you would need instead.

Show the answer

XOR cancels a number only when it appears an even number of times. Three copies of a number leave one copy after XOR, so the result is wrong. The version with three copies needs a count per bit column, taken modulo 3 (the remainder after dividing by 3). For each column, add up the bits across all numbers, take the total modulo 3, and set that column of the answer to the result.

11. (Hard) Write the Gray code of a number i as i ^ (i >> 1), and find the Gray code of 3 and of 4. Explain why adjacent Gray codes differ in one bit.

Show the answer

The output is:

3 011 2 010
4 100 6 110

The codes 2 and 6 differ in exactly one bit. Adding 1 to i turns its trailing ones into zeros and the first zero above them into a one. Working through i ^ (i >> 1) shows that only one bit of the code changes, at the position of that first zero. The rule that adjacent Gray codes differ in one bit holds for the whole sequence, and it is why Gray codes are used in rotary sensors, where a misread bit must not jump the reading by many steps.

What you now know

• A number is a row of bits. Each column is a power of two, counted from 0 at the right.
• Python shows negative numbers with a minus sign, and the bit operators treat them as an endless row of leading 1s. ~n equals -n - 1.
• & keeps columns where both bits are 1, | keeps columns where either bit is 1, and ^ keeps columns where the bits differ.
• << doubles for each place, and >> halves and keeps the sign. Python has no >>>, so mask a value first for an unsigned shift.
• Masks read, set, clear and toggle single bits. Brackets make the intent clear in comparisons.
• n & (n - 1) removes the lowest set bit, which gives the power-of-two test and the bit count.
• XOR cancels pairs, and x ^ x is 0.
• The midpoint lo + (hi - lo) // 2 avoids the overflow that a fixed-size type can cause.
• Python integers do not wrap around, and a negative shift count raises an error.