Shifts on negative and unsigned values in Python

Why this matters

A shift moves every bit of a number a fixed number of columns to the left or to the right. Shifts are fast, and programmers use them to multiply and divide by powers of two, to read fields packed into a number, and to mix bits in hash codes. Python has two shift operators, << and >>. The first is easy to understand. The second keeps the sign of a negative number, and Python has no third operator that fills with zeros. Many languages have that third operator, such as Java's >>>, and a program ported from one of them must replace it. This lesson shows how.

The earlier lessons on bitwise operators and on popcount cover the other bit tools. Here the only question is what happens to the leftmost column when a value moves right.

Shifting a positive number

Start with a small positive number. The number 20 is 10100 in binary. The columns, from the right, are worth 1, 2, 4, 8 and 16. So 20 = 16 + 4.

Shifting right by 2 moves every bit two columns toward the 1 column. The two rightmost bits fall off the end. Each remaining bit moves down by two places.

20      = 10100
20 >> 2 = 00101  = 5

Shifting right by 1 divides by 2 and drops the remainder. Shifting right by 2 divides by 4 and drops the remainder. The number 20 divided by 4 is 5, so 20 >> 2 is 5.

The output is:

20 >> 2 = 5
20 // 4 = 5

For a positive number, a right shift is the same as floor division by a power of two. The difference only appears when the number is negative. Python shows a negative number with a minus sign, but its bits behave as if they go on forever to the left. The sign is the bit that repeats in that row: 1 for a negative number, 0 for a positive one.

The sign column decides everything

The bits of a negative number are easiest to see with a fixed width. The helper below writes the low 32 bits of any integer, using the mask & 0xFFFFFFFF to keep only those columns. Here is the bit pattern for -8. The leftmost column is 1 for every negative number in a 32-bit view. The number -8 is 29 ones followed by 000:

The output is:

bits of -8 = 11111111111111111111111111111000

Think of the 32 columns as a row of light switches on a wall. The leftmost switch is the sign. A right shift moves each switch one place toward the right, and it opens a new switch on the far left to fill the gap. Python's >> puts a copy of the sign into that new switch, so a negative number stays negative. A shift that fills with zeros is the unsigned shift. Python does not have one, but the mask gives the same answer: first keep the 32 columns with & 0xFFFFFFFF, which turns the negative number into a plain positive pattern, then shift that pattern.

The output is:

-8 >> 1 = -4
unsigned -8 >> 1 = 2147483644
bits of the unsigned result = 01111111111111111111111111111100
-8 >> 2 = -2
unsigned -8 >> 2 = 1073741822

Look at neg >> 1. The bits moved one column right, and the new leftmost column copied the sign, which was 1. The result is -4. That is the answer you want when you divide a negative number by 2, rounded down.

Look at (neg & M32) >> 1. The mask turned -8 into the 32-bit pattern, which has a 1 in the sign column. The shift moved the bits right and put a 0 in the new leftmost column. The result is 01111111111111111111111111111100, which is 2147483644. The sign has been lost, and the value is no longer -4.

Neither answer is wrong. Each one follows its own rule. The mistake is to use one when you meant the other.

Shifts with all ones

The contrast is clearest with -1, which is 32 ones in a 32-bit view. Every shift of -1 by >> copies a 1 into the new columns, so the result stays -1. A shift of the masked value brings in zeros.

The output is:

-1
1
15

Shifting by 31 leaves one column. With >>, that column is a copy of the sign, so the answer is -1. With the mask, the 31 zeros come in on the left, and the only bit left is the sign that was moved to column 0, so the answer is 1. The third line is (-1 & M32) >> 28. Four columns remain, and all of them are 1, which is 15.

To predict any right shift of a negative number by hand, take the 32 bits, drop the bits that fall off the right end, and put a block of new bits on the left. The block has as many columns as the shift distance. For >> each new bit is a copy of the sign, so it is 1. For the unsigned view each new bit is 0. With -8 >> 2, the bits 11111111111111111111111111111000 lose their last two columns, which leaves 111111111111111111111111111110, and two copies of the sign go on the left. The result is 11111111111111111111111111111110, which is -2.

A simple rule covers most cases. Use >> when the value is a quantity that can go below zero, such as a temperature or a balance. Use the masked form when the value is a pattern of bits, such as a set of flags, a colour field or a hash.

Right shift rounds down, and so does //

For negative numbers, >> gives the same answer as //, which rounds toward negative infinity. It does not give the same answer as int(a / b), which cuts toward zero. The program below shows the three results for -7 and 2:

The output is:

-4
-4
-3
-1

The exact value of -7 divided by 2 is -3.5. Truncation toward zero gives -3. The shift and // round down to the next whole number below -3.5, which is -4. The lesson on floor division and modulo covers this rounding rule in full. The point here is that >> and int(a / b) are not the same operation for negative numbers, even though both look like they divide by 2.

The unsigned idea in practice

Python has no unsigned integer type, and every integer has a sign. The masked form is how a Python program treats the 32 bits as a plain row of columns with no sign. This is useful when a number is really a bit pattern, not a quantity.

A common case is a hash code, which is a whole number made from a value's contents. The number 0x9E3779B9 is used here as a sample value, not a real hash. Java's HashMap mixes the high bits of a hash code into the low bits by XOR-ing the value with a copy of itself shifted right by 16. XOR (exclusive or) gives a 1 in each column where exactly one of the two bits is 1. This spreads differences from the top of the number into the bottom, where the table index is taken from.

The output is:

h            = 9e3779b9
h >> 16      = 9e37
h ^ (h >> 16) = 9e37e78e

In Python, 0x9E3779B9 is a positive number, so >> already gives the answer a Java >>> would give. The Java version of this value is negative, because its leftmost bit is 1. The c_int32 type in the standard ctypes module gives the signed 32-bit value that Java would hold:

The output is:

signed h = -1640531527
signed h >> 16 = -25033 ffff9e37
unsigned view >> 16 = 9e37

The signed shift fills the top 16 columns with 1s, which gives ffff9e37 in the low 32 bits. Those ones would flip the top half of the result when XOR is applied. The unsigned view fills the top with zeros, which gives 9e37, and the XOR then mixes the two halves without adding extra ones. This is why the unsigned view is the right tool for this job.

The XOR operator is covered in the XOR tricks lesson. The point for this lesson is simple. When the bits are the data, mask the value to its width before you shift.

Shifts on bytes

A byte holds 8 columns. Python has no byte type in ordinary arithmetic, and a value such as -8 is an integer with a sign. To read a byte-sized field as unsigned, mask it with & 0xFF before the shift, and the mask keeps the 8 columns the byte had:

The output is:

-4
124
2147483644

The first line is -4, because >> keeps the sign. The second line masks the value with & 0xFF first. That keeps only the 8 columns of the byte, so the result is 11111000 shifted right to 01111100, which is 124. The third line uses the 32-column mask, and gives the same 32-bit unsigned view as before.

This is the usual way to read a byte as an unsigned value. Mask it with & 0xFF, then shift.

Python has no compound unsigned shift for a byte. The compound form b >>= 1 stores the result as an ordinary integer, so the value does not turn back into 8 columns:

The output is:

-4

How far a shift can move

The number of columns to shift is called the shift distance. In Java, the distance is taken modulo the width of the type, so 1 << 32 is 1 for an int. Python has no width, so the distance is not reduced at all:

The output is:

2147483648
4294967296
8589934592
18446744073709551616
-1

The value grows as the distance grows, because Python integers grow as needed. A negative distance is a different case, and Python refuses it with an error:

The output is:

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

The file path in the first line depends on where you save the file. Keep the distance non-negative in real code. If a shift distance can be large, check that it is within the width of the value you want, because a large shift of a small value gives a large number.

A summary table of the results

The table gathers the results from this lesson in one place. Each row uses an integer, and the 32-bit column shows the unsigned view where a mask was used.

Reading packed fields

Programs often pack several small numbers into one integer. A colour is a common example. A 32-bit colour value in the ARGB form uses 8 columns each for alpha (how opaque the colour is), red, green and blue. Alpha is the leftmost byte, so it is where the sign lives in a 32-bit view.

The output is:

alpha >> 24 = 255
alpha signed >> 24 = -1
alpha masked = 255
red = 128
green = 64
blue = 192

The alpha byte of 0xFF8040C0 is 11111111. In Python, the number is positive, so argb >> 24 gives 255 directly. A Java int holding the same bits is negative, and its >> would give -1. The ctypes.c_int32 conversion reproduces that Java value, which is why the second line gives -1. The mask & 0xFF after the shift keeps only the 8 columns of the field, so the answer is 255 in either case.

The same trap appears with a value that has alpha 128. Here 0x80402010 >> 24 is 128 in Python, and the signed 32-bit value shifted by 24 is -128. The mask makes the answer 128 in both cases:

The output is:

128 128
-128

Common mistakes

Using >> to walk a negative number to zero

A loop that walks through the columns of a negative number with >> never ends, because the sign keeps copying itself in. The program below sets a limit of 40 steps, so that it can finish:

The output is:

loop with >> on -16 stopped after 40 steps, x = -1

The loop condition x != 0 never becomes False, because x settles at -1. The count < 40 check was added only to stop this test. Mask the value to 32 bits first, and the loop reaches 0 after 32 steps:

The output is:

masked loop stopped after 32 steps, x = 0

Expecting a byte to behave like an unsigned value

-8 >> 1 is -4, not 124, because Python keeps the sign. Mask the value with & 0xFF first, as shown above.

Assuming a shift result has a fixed width

In Java, a shift of a long gives a long, and assigning it to an int fails to compile. Python has no fixed width for ordinary integers, so the assignment x = 1 << 40 works. A value that must fit in 32 bits needs a mask or a ctypes type:

The output is:

1099511627776
0

The ctypes.c_int32 type keeps only the low 32 bits. The value 2 to the power 40 has zeros in those bits, so the result is 0.

Practice

1. What is -16 >> 2? What is (-16 & 0xFFFFFFFF) >> 2? Work out both by hand, then check with a program.

Show the answer

The value -16 is 11111111111111111111111111110000 in a 32-bit view. Shifting right by 2 with >> copies two 1s into the top, so the result is 11111111111111111111111111111100, which is -4. With the mask, the two new columns are 0, so the result is 00111111111111111111111111111100, which is 1073741820. A program prints -4 and 1073741820.

2. Write one expression that gives the value of a byte-sized integer b as an unsigned number from 0 to 255. Test it with b = -1, which should give 255, and b = 64, which should give 64.

Show the answer

The expression is b & 0xFF. The & 0xFF keeps only the 8 columns of the byte, and it clears the columns above them that a negative number has. For -1, -1 & 0xFF is 255. For 64, 64 & 0xFF is 64.

3. Predict the output of print((-1 & 0xFFFFFFFF) >> 33).

Show the answer

The masked value has 32 columns, and a shift of 33 moves every one of them off the end, so the result is 0. In Java, >>> would take the distance 33 modulo 32, and the answer would be 2147483647. The difference comes from the fixed width.

4. Write a function unsigned_high(n) that returns the top 4 bits of a 32-bit pattern as a number from 0 to 15. Test it with 0xF0000000, which should give 15, and with 0x40000000, which should give 4.

Show the answer

The output is 15 4. The top four columns are the four bits in positions 31 down to 28. Shifting right by 28 leaves those four bits in the lowest columns and fills the top with 0s.

5. Explain in one sentence why -7 >> 1 is -4 and not -3.

Show the answer

The right shift rounds the exact value of -3.5 down to the next whole number below it, which is -4, while int(-7 / 2) cuts toward zero and gives -3.

Summary

• >> copies the sign bit into the new leftmost columns, so a negative number stays negative.
• Python has no >>> operator. Mask a value with & 0xFFFFFFFF to get the unsigned 32-bit view before a shift.
• For positive numbers, >> gives the same result as floor division by a power of two.
• A byte-sized field is read as unsigned with & 0xFF, and ctypes types give fixed-width values when a program needs them.
• Python integers do not wrap, so a shift distance is not reduced, and a negative distance raises ValueError.