In this segment we'll discuss the effect of shifting bits left and right within a binary number.
As we'll see in an upcoming code example, many ARM assembly instructions permit bit shifting -- moving the bits in a register, or in a constant binary value, some number of positions to the right or to the left. For instance, here is a 16-bit example, shifted to the right and also to the left by 5 bits.
0101001111010001 # Original value 0000001010011110 # Value shifted right 5 bits 0111101000100000 # Value shifted left 5 bits
In each case, 5 bits are lost as they are shifted off one end, either right or left. And 5 0-bits fill in on the opposite side.
Bit shifting can be used to create and analyze bit patterns within a register. We'll see examples of this in an upcoming program. But bit shifting also has a mathematical effect, which we'll look at here.
Question 1
Consider these unsigned 8-bit examples of shifting left by one bit: 00000110 left-shifted to 00001100, and 00101010 left-shifted to 01010100. What, exactly, are their numerical values before and after left-shifting? What does this suggest about the mathematical effect of left-shifting?
Answer 1
It makes sense that left-shifting would multiply a number by 2 when you see that each bit is moved up one position, and thus has 2x the numerical value it had before shifting. The same sort of multiplication occurs when shifting a base-10 number left by one digit, e.g. 123 left-shifted to 1230. Each digit has 10x its preshifted value, and the number is multiplied by 10.
And, left-shifting by more than one position repeatedly doubles the value, redoubling as many times as we left-shift.
Given that the 8-bit pattern for 5 is 00000101, what is the pattern for 80 (5*16)? Do this by left-shifting.
Answer 2
If shifting left doubles a value, then shifting right divides it by 2, since each bit moves to a position that is half as valuable. For instance, 01000110 (70) shifts right to become 00100011 (35).
But right shifting is more complex in two ways. First, consider what happens when we shift an odd value, say 00000111 (7). The result is 00000011 (3), and the rightmost 1 is lost. The effect is that the division of 7 by 2 is truncated from 3.5 to 3. Rightshifting divides by 2, discarding any fraction.
Since we're talking about shifting bits off the bottom end of a number, it's worth noting that binary arithmetic can be extended into fractional places, just like decimal. The decimal system has a 1/10ths place, 1/100ths place, etc. to represent fractions with arbitrary accuracy to the right of the decimal point. We can do the same thing in binary, adding a "binary point", with positions after it representing 1/2, 1/4, etc. If we do that, then shifting 00000111 to the right gives 00000011.1 which is binary for 3.5, since the ".1" represents 1/2. Shifting right again would yield 00000001.11, which is 1.75 since .11 is 1/2 and 1/4.
Using fractional binary places, how would you write 1.625 (or 1 5/8)?
Answer 3
We'll look more at binary fractions when we discuss floating point numbers later in the course. For now, all fractional bits are simply dropped when we right shift.
The second complexity with right-shifting shows up when right-shifting signed negative numbers. Consider the case of right-shifting 11111100 to get 01111110. The division-by-2 rule works fine, if they're unsigned: 252 shifts right to become 126.
But, what about the signed case: What are the signed values of 11111100 and 01111110?
Answer 4
In order to preserve the mathematical effect of division by 2 when right-shifting a signed value, we have to use sign extension -- filling in on the left with whatever the MSB is. In particular, when we right shift a negative signed value, we fill in on the left with 1's.
If we're shifting to the right to divide by powers of 2, then sign extension is appropriate. If we're more interested in the bit patterns than in the mathematical value, then extra 1-bits on the left are a nuisance. Almost all assembly languages, including ARM, let you choose between a logical right shift which does no sign extension, and an arithmetic right shift which does.
All the shifts we've done so far simply dropped bits off of the right or left end. But there is another possibility. In a right shift, for instance, we could move bits shifted off the right back around to the left end of the number, in circular fashion, almost as if the bits were on some kind of a chain. So, right shifting 01100101 by say 3, yields 10101100, with the bottom three bits rotating back to the left end instead of being dropped.
Most CPUs, including ARM, offer this shifting option, but it's less common than the others because it lacks a clear arithmetic meaning.