3

It is true that the bitwise left shift operation (shl) doubles the value of the integer being shifted. However, when constrained to a finite space, such as 8 bits for example, left shift will begin to push bits off the high-order word and will cause loss. What mathematical effect does this loss have on the number? Does it somehow cancel the doubling effect of the shift?

A related operation is the rotate left operation (rol), in which this loss does not occur.

  • It certainly won't "cancel the doubling effect of the shift". Rather than worry about finding a mathematical name for the effect, why don't you explore it and gain a hands on sense of what happens? The 8 bit case is easy to generate a table for by any of manually, with a small program, or even a spreadsheet... – Chris Stratton Mar 18 at 21:02
  • 1
    A shift left beyond allocated bit space results in an overflow. A shift right results in an underflow. At the CPU level, left and right shifts usually have an option to set a "carry" flag when one of these occurs, in which case the bit that would have been lost is moved into the flag instead. – John Wu Mar 19 at 1:39
1

Let’s generalize:

Suppose that you have n+1 digits, noted D0 to Dn starting with least significant one (i.e. starting on the right in our numeral conventions). Suppose that R is the radix used, so that every Di has a value between 0 and R-1.

The mathematical value V expressed by the sequence of digits is the sum (for i=0 to n) of Di*R^i (where ^ expresses the power operation).

Examples, wit V expressed in decimal:

R=10. D=265. V=5+6*10+2*100=265
R=16. D=A2.   V=2+A*16=2+10*16=162
R=2.  D=101.   V=1+0*2+1*4=5

You can then easily demonstrate that shifting any such numbers in radix R to the left by introducing and additional 0 digit on the right means multiplying its value by R.

R=10. D=265.   V=265.  26550 is V*10 
R=16. D=A2.     V=162.  A20 is V*16
R=2.  D=101.    V=5.      1010 is V*2

So in a binary system, with bits being in radix 2 the shift left is multiplying by 2.

But no hardware works with infinite number of bits

When you use unsigned numbers, and if you have a maximum of n+1 digits, then for any number with Dn not null (so greater or equal than R^n), shifting to the left once more means to lose the highest digit of value Dn*R^n

Example:

R=10  n+1=3  D=801 => 010 so V*10-8*100
R=2.  n+1=8. D=10000101 => 00001010 so V*2-1*128

Now thing are more complex for signed numbers. Here, in mathematical notation, the sign is always an extra information that is never confused with digits.

But in a computer, the sign is represented by a bit (generally the most significant one) and anyway the other bits may represent a two’s complement for negative numbers.

I let you also as a simple exercise to calculate the rotation effect.

I let you as a more advanced exercise for a given binary encoding of signed number to calculate the effect of shifting when it affects the sign bit.

2

Bitwise shift is a pretty basic implementation. It is true that it doubles the value of unsigned integers. But that is not the case for other types of data. In the case of two's complement for example, it could change the sign of the number as well as the value. If the values bytes represent ascii characters, shift left will convert ' ' (0100000) to '@' (1000000).

The only thing that changes with shift left with larger numbers of bits is, how many bits there are to shift (obviously) and which position is the last one you can shift a bit to. This is dependent on the language and/or instruction set. In Java, for example, there is no difference between the behavior of a left-shift between 32-bit and 64-bit architectures. That is defined as part of the language spec and does not vary based on the architecture of the machine it runs on.

0

If we assume that the data is treated an an unsigned number, then the result is a doubling, but under modulo arithmetic. So

y = (2x) modulo N

For an 8 bit number, that would be modulo 2 to the power 8, or modulo 256. For a 16 bit number it would be modulo 65536.

Modulo N arithmetic can be thought of as implementing the rule "if the result is greater than or equal to N, keep subtracting N until the result is less than N".

For the 8 bit case:

1 shifted left gives (2 modulo 256) = 2.
65 shifted left gives (130 modulo 256) = 130.
129 shifted left gives (258 modulo 2) = 2.

For shifts of more than one place, you can keep doubling and apply the modulo at the end. Or keep doing the double then modulo. It comes to the same thing.

It all gets complicated with signed arithmetic. You have to interpret the number in whatever signed convention the processor uses, usually 2's complement. Some processors even have different implementations of left shift for signed and unsigned numbers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.