Binary Shifts

A binary shift moves the bits in a binary pattern a set number of places to the left or right. The pattern keeps its fixed width, so any bits that move past either end are discarded rather than reappearing at the other side.

For example, shifting the 8-bit pattern 0011 1010 left by two places discards the two leftmost bits (00). Zeros fill the two right-hand vacancies, giving 1110 1000. The original value 58 has been multiplied by 4 to give 232.

Vacant positions are filled according to the type of shift. A logical shift fills every vacant position with a 0. An arithmetic right shift fills the left-hand vacancies with a copy of the sign bit (the most significant bit), so the sign of a signed integer is kept. A left shift, whether logical or arithmetic, fills the right-hand vacancies with zeros.

Shifts are a quick way to multiply or divide by powers of two. Shifting left multiplies: one place doubles the value, two places multiplies by four, three places by eight, and so on. Shifting right divides: one place halves, two places divides by four, three places by eight. The multiplier or divisor is 2 raised to the number of places — two places means 2² = 4, not 2.

A logical shift slides the bits of a binary pattern a number of places to the left or the right, and fills every position left empty with a zero. The pattern keeps the same width, and any bits pushed past the edge are lost rather than wrapped round to the other end.

Which side takes the zeros?

The direction of travel tells you which end needs filling: the gaps always appear behind the moving bits.

Take 0011 0100, which is 52. Shifting it one place left moves every bit up a place value and puts a 0 in the right-hand gap, giving 0110 1000, which is 104. Shifting it one place right does the opposite: the bits step down a place value, a 0 fills the left-hand gap, and 0001 1010 is left, which is 26. If a 1 sits at the very edge when it moves, it drops out of the pattern and is discarded.

Why unsigned integers use logical shifts

In an unsigned integer every single bit is a value bit — none of them is reserved for anything else — so a zero dropped into a gap can never spoil the number, and the shifted pattern is still a valid unsigned value. Filling with 0 is simply the safe choice. A signed integer stores its sign in the leftmost bit, so a zero in the left-hand gap would not do; signed numbers use the arithmetic shift instead.

An unsigned integer is stored as a binary pattern in which every bit adds to the value. Moving that pattern sideways is called a shift, and it gives a quick way to multiply or divide by powers of two without carrying out a full calculation.

One place at a time

A left shift by one place moves every bit one position to the left, so each bit lands on a place value twice as large. The whole value therefore doubles. Starting with 00001101 (13), a left shift gives 00011010, which is 26.

A right shift by one place moves every bit one position to the right, so each bit lands on a place value half as large. The value halves. If the number is odd, the 1 bit that drops off the right-hand end is lost, so any remainder is discarded: 00001101 (13) shifted right becomes 00000110, which is 6, because 13 ÷ 2 = 6.5 and the 0.5 is thrown away.

Several places at once

Each place you move doubles or halves the value again. A left shift by n places multiplies by 2 to the power n, and a right shift by n places divides by 2 to the power n, discarding any remainder. So two places means multiply or divide by 4, and three places means multiply or divide by 8.

Using the same 8-bit pattern 00001101 (13):

The direction decides whether you multiply or divide, and the number of places decides which power of two you use. A left shift by three on 00001101 gives 01101000 (104), which is 13 × 8. A right shift by three gives 00000001 (1), because 13 ÷ 8 = 1 remainder 5, and that remainder is discarded.

An arithmetic shift moves a binary pattern left or right. It is the shift you use for signed integers, such as two's complement numbers, because a right shift keeps the sign of the number the same. The bit that carries the sign is the leftmost bit, the most significant bit (MSB).

Shifting right

An arithmetic right shift moves every bit one place to the right and copies the sign bit into each vacant position on the left. Because the sign bit is copied rather than replaced, the sign is preserved: a negative number stays negative and a positive number stays positive.

Each place shifted right halves the value, so n places divide it by 2^n, discarding any remainder. For example, take −46 as the 8-bit pattern 1101 0010. Shifting right one place copies the 1 from the MSB into the gap, giving 1110 1001, which is −23 — exactly half of −46, still negative.

Shifting left

An arithmetic left shift moves every bit to the left and fills the vacant positions on the right with zeros. This makes it identical to a logical left shift, because a logical left shift also fills with zeros; there is nothing to preserve at the right-hand end.

Each place shifted left doubles the value, so n places multiply it by 2^n. For instance, 1101 0010 (−46) shifted left one place becomes 1010 0100, which is −92.

Why the fill bit matters

A logical right shift on a negative two's complement number forces the sign bit to 0, so the answer is wrong for a signed integer: 1101 0010 (−46) shifted logically right one place gives 0110 1001, which is 105. The only difference between the two right shifts is that single fill bit.

A binary pattern has a fixed width, such as 8 bits. When a shift moves a bit past either end, that bit is gone: it is not wrapped round to the other end. This matters because the value you keep can be smaller or less exact than the true result.

Right shifts lose accuracy

A right shift divides by a power of two, but the bits that fall off the right-hand end are discarded. For a positive number this means the result is rounded down. For example, the 8-bit unsigned pattern 00110101 (53) shifted right by one place becomes 00011010 (26). The final 1 is discarded, so 53 ÷ 2 = 26.5 becomes 26.

For an arithmetic right shift of a negative two's complement number, the effect is to round towards negative infinity. The 8-bit pattern 11111001 represents -7. Shifted right by one place it becomes 11111100, which is -4. The true answer -3.5 has been rounded down, not towards zero.

Left shifts can overflow

A left shift multiplies by a power of two, but any 1 bits pushed beyond the most significant bit are lost. If this changes the value, the shift has caused overflow. For example, the 8-bit unsigned pattern 10011100 (156) shifted left by one place becomes 00111000 (56). The leading 1 has been shifted out of the fixed-width pattern, so the result is not 312.

The result of any shift therefore depends on its direction, how many places it moves and the fixed width of the pattern.