Recently I was listening to a
retrocomputing-themed
podcast, as I am often wont to do... This particular podcast has a recurring segment wherein a game developer from
the good old days is presenting some relatively simple lessons on programming in
assembly language for the
Motorola 6809. This particular lesson was about
shift and rotate instructions, which are used both for manipulation of data bits within a data byte and for performing the fundamental operations of multiplication and/or division by exact powers of the number 2.
I do not intend to critique the presentation as a whole. But there was one bit of misinformation presented that I feel the need to address. During the talk, the fact was mentioned that when designing the instruction set for the 6809, Motorola had chosen to implement both logical-shift-left (LSL) and arithmetic-shift-left (ASL) with the same physical machine instruction. The assertion was that this was wrong, that LSL and ASL are different operations, and that due to Motorola's failure to recognize such, one should
never use that instruction. This assertion being made by one acting in a teaching capacity is so clearly wrong that I feel compelled to clarify the record.
Did the CPU architects at Motorola get it wrong?
Spoiler alert: No! Neither did architects for Intel, MIPS, Sparc, ARM, or any of the other CPUs that similarly implement a single instruction for both operations. The fact is that when operating on
two's-complement numbers, logical-shift-left and arithmetic-shift-left are, in fact, exactly the same operation.
Signed Binary
This (supposed) controversy is rooted in how negative numbers are represented in digital computers. As you are probably aware, digital computers represent numbers using
binary numbers. For positive, whole numbers the mapping to representation in binary is obvious. But there is no obvious extension to binary numbers to account for either fractional or negative numbers. (Fractional numbers are outside this particular conversation...)
Negative numbers can be represented in binary in at least three ways:
two's complement (which nearly every digital computer uses),
one's complement, and
signed magnitude, among others. Two's complement encoding has the advantage that basic operations like addition and subtraction between signed and unsigned values "just work" with the same hardware that is already needed for unsigned operations. Plus, two's complement does not suffer from having multiple ways of encoding the number zero. Consequently, two's complement is the encoding system used by Motorola on the 6809 (and most other designers on most other digital computers up to this day and beyond).
One point to note: although for human communication we usually do not write leading zeros on numbers, most of us are at least vaguely aware of the idea of them. More importantly, computers tend to have fixed-width places to store numbers, like registers or bytes in memory. In those cases, every bit (leading or otherwise) is either a zero or a one. For the discussion below, it is important to realize that positive numbers will start with one or more (i.e. possibly several) leading zeros while negative numbers will start with one or more (i.e. possibly several) leading ones.
Logical vs. Arithmetic
As noted above, shift operations can be used to manipulate isolated bits of information stored within a larger byte. But they can also be used for power-of-2 multiplication and division. The former of those two categories is called logical shifting, while the latter is called arithmetic shifting. The appropriate handling of the leading zeros and ones in two's complement numbers accounts for the differences between the two type of shifting.
In logical shifting, the bits in a byte are shifted left or right as a group like beads on an
abacus. Bits farthest in the direction of the shift effectively "fall off" that edge, and they are replaced by zeros entering from the opposite side. This mechanical manipulation of bits can be quite useful when converting small data values embedded in "
bit fields" to and from actual register values usable for math operations on the CPU. Nevertheless, careless application of logical shifts could prove quite destructive to a two's complement number where adding a zero at the wrong end could drastically change the meaning of the binary value.
Arithmetic shifting preserves the sign (i.e. positive or negative) aspect of a two's complement number while still transforming its magnitude. Right shifts reduce magnitude (i.e. numbers get closer to zero), while left shifts increase magnitude. So, how is this magic performed?
For a shift to the right, the rightmost bit is dropped leaving the leftmost bit temporarily vacant. For a logical shift, the vacant leftmost bit is filled with a zero -- but this would be wrong for a two's complement number. For example, -128 shifted right would become 64!
10000000 --> _1000000 (left bit vacated)
--> 01000000 (filled with zero -- wrong!)
In order to maintain the sign of the shifted value, an arithmetic shift to the right will replicate the value of the leftmost bit. This yields correct values for both positive and negative two's complement values.
10000000 --> _1000000 (left bit vacated)
--> 11000000 (filled with one -- correct!)
Notice how continued shifts will increase the number of leading ones as the magnitude of a negative number decreases (i.e. gets closer to zero):
--> 11100000 (-32)
--> 11110000 (-16)
--> 11111000 (-8 )
--> 11111100 (-4 )
--> 11111110 (-2 )
--> 11111111 (-1 )
So we see now that the sign must be preserved while shifting. So what does an arithmetic shift to the left do to preserve the sign? Let's visualize by implementing the above table in reverse:
11111111 (-1 )
--> 11111110 (-2 )
--> 11111100 (-4 )
--> 11111000 (-8 )
--> 11110000 (-16 )
--> 11100000 (-32 )
--> 11000000 (-64 )
--> 10000000 (-128)
As you can see, the arithmetic left shift is done by dropping the leftmost bit, shifting every other bit to the left, and filling the vacated bit on the right with a zero. While no action is taken to preserve the sign bit, it is nevertheless maintained at the same value by subsequent leading ones. Positive values are handled the same way, with equally correct results. In either case, the magnitude of the result (i.e. the distance from zero) is increased.
With that explained, please demonstrate for me how an arithmetic left shift on a two's complement binary number differs in any way from a logical left shift. I'll wait...hopefully we now agree that arithmetic left shift and logical left shift are the same operation!
Carry and Overflow
By now, some of you will have had an "
a ha!" moment...what happens when a value is such that the leftmost (i.e. sign) bit isn't re-filled properly by the following bit in the left shift? This can happen, but only for values between -65 and -128 -- feel free to do some two's complement encoding exercises to convince yourself of this fact, if necessary. Multiplying those values by two (i.e. the purpose of the arithmetic left shift) would yield values that are too large to fit in a byte anyway. At that point, no amount of maintaining the sign would undo the fact that the resulting value would still be wrong.
So what is done in this case? Well for one thing, the bit that gets dropped off the left of the value is retained in the Carry flag, where it can be retrieved by a following rotate operation. This facility can be used to shift the "lost" bit onto the right side of the next byte in a multi-byte value. This operation is quite common when handling multi-byte values.
The other thing that happens when a "too negative" value (i.e. a negative value with too large a magnitude) is shifted left is that the oVerflow flag is set. By checking the V flag after a left shift, one can determine whether or not the sign of the value is changed by the shift. At that point, the programmer can take whatever action is deemed appropriate either to fail the operation or to correct the apparent error.
Above I have demonstrated that for two's complement binary numbers, the mechanics of a logical left shift and an arithmetic left shift are exactly the same. This is not controversial, and would never have been in question had it not been for some random comments on a podcast. Given that the comments in question amount to misinformation and that said podcast has an audience which significantly overlaps with
my own podcast, I felt it necessary to provide a defense of the facts with the demonstration above. Feel free to do your own research, but what I have presented above is absolutely true.
For further reference:
https://en.wikipedia.org/wiki/Bitwise_operation
https://open4tech.com/logical-vs-arithmetic-shift/
http://teaching.idallen.com/dat2343/09f/notes/04bit_operations_shift.txt
Hopefully that proves the point...Q.E.D.
