Another circuit, called the shifter, is extremely important. Shifters simply copy their input wires to their output wires, making a slight permutation of the values, usually displacing the output one bit either to the left or the right. Suppose that we had an 8-bit register and ran its value through a 1-bit left shifter. If the value is 10101101, the result would be 01011010. The leftmost bit is lost, dropped into the proverbial "bit-bucket" (which has an infinite capacity) and a 0 is inserted at the right end. If the shift were 1 bit to the right, the result would be instead 01010110. Again a 0 is inserted at the end from which the shifting starts.
Fig. 6.7.1 shows a circuit that performs a 1-bit right shift or a 1-bit left shift. Note the two wires that are connected to logic 0 all the time, which are used to insert those 0s at the ends.
The shifts described above are called logical shifts and can be 1, 2 or more bits, although it is uncommon to see a shifter than can shift more than 4 bits at a time. Most computers make do with 1-bit shifters and do several shift instructions in a row in order to accomplish a multi-bit shift.
There are two other shifting types besides logical shifts. Here is a complete list. All of these can be 1, 2, or more bit shifts and can be left or right.
| logical shift | 0s are inserted at the end, bits drop off and disappear from the opposite end |
| circular shift | bits taken off one end are inserted at the other |
| arithmetic shift | this is like a logical shift except the sign bit is always copied into the output. |
Circular shifts are sometimes called rotating shifts because they form a kind of circle of bits. The value of a register is not lost if it subjected to a series of circular shifts. In fact, if an n-bit register is circularly shifted n times, it will wind up with the original value. This is not true with logical shifts since bits are constantly getting lost at one end and 0s are inserted at the other. To set an n-bit register to 0, subject it to n logical shifts, either left or right.
Following are a number of shifts:
Original 1-bit left 1-bit right 1-bit left 1-bit right
logical logical circular circular
--------------------------------------------------------------------------
10010111 00101110 01001011 00101111 11001011
00000001 00000010 00000000 00000010 10000000
10000000 00000000 01000000 00000001 01000000
11111111 11111110 01111111 11111111 11111111
00011000 00110000 00001100 00110000 00001100
Notice that if we treat the bit strings as unsigned integers, then left logical shifts seem to perform multiplication, while right logical shifts perform division. For example, 00010111 is 23, and 00101110, the result of a left logical 1-bit shift, is 46. If we shift 00010111 two bits and get 01011100, the value is 92, or 23x4. Thus, the number of shifts is the power of 2 by which the unsigned number is multiplied. However, if 1s are lost off the left end, the result will be less than the original number, which signifies yet another form of overflow. In all cases, overflow is a result of not having enough bits to store a value, and it always occurs in this world of finite machines.
Right logical shifts are divisions by 2, but it is integer division with truncation. For example, 23/2 is 11.5, or just 11 if we truncate, and indeed 00001011 is 11. Right logical shifts can never result in overflow because the new number resulting from the shift or division is always smaller than the original. But information is lost nonetheless because decimal places are eroded away until the result is 0.
The arithmetic shift seems a bit stranger at first until we realize that the idea is to preserve the sign of 2's complement numbers, which is useful when using shifting to emulate multiplication and division of signed integers. To do an arithmetic shift, remember the original value of the MSB (most significant bit, which is the leftmost bit), then do a logical shift, inserting 0s on the left or right end, depending upon whether the shift is right or left. Then copy the original sign bit into the MSB. Here are some examples using 8-bit words:
Left arithmetic shift Original value Right arithmetic shift ------------------------------------------------------------------- 01011010 00101101 00010110 11110100 11111010 11111101 10111010 11011101 11101110 10111010 10011101 11001110
An odd thing happened in the last example. 10011101 is -99 in decimal if we treat 10011101 as an 8-bit 2's complement number. However, 10111010 is -70, which is not -99 x 2! But wait! -99 x 2 would be -198, yet we can only represent negative numbers down to -128. So arithmetic shifts are subject to that old nemesis, overflow.
A rather whimsical way of viewing arithmetic right shifts is to imagine the bit string as encoded on a rubber band and the left end is anchored to a wall. Pull as we might, we cannot dislodge the MSB from the wall, but it just stretches. So the 1s copy themselves into bit places to the right, as do 0s if the number were originally positive. In a similar vein, an arithmetic left shift is like pushing a piece of paper into a wall. It crumples up against the wall, the left end of the bit string, and does not change the wall.