What was the main purpose of bitshift instructions in CPU?

Question

As far as I know, even simple RISC microcontroller have a bitshift operator, and honestly I had to use it only once when I had to compute a division on a MCU that could not do divisions in the ALU.

Were the bitshift operators included so it was possible, even with very simple ALU, to efficiently compute the multiplication, the division and the square root?

I'm wondering this because that was how it was done on mechanical calculators, so looks plausible to me that first processors somewhat mimicked existing technologies.

EDIT

I'm not asking what are the use of bitshift operators, but the reason why they were included back then. As every operation added had a cost in components, I imagine that they were striving for the smallest possibile number of components.

So the question is whether the bit shift operators are an innovation added when computers were put on a chip or whether very early CPUs also had these operators. And if so, why were they included in the instruction repertoire of early CPUs? What value did they add? (paragraph proposed by Walter Mitty)

My line of thought was that, since early computers were created to speed up the work made by human computer, who used mechanical calculators (which shift values to perform calculations), it was plausible to me that electronic computers were designed to use, at least partially, existing algorithms. I made this question because I wanted to know if there is some truth in this or I was completely wrong.

Answer 1

Some uses for a bitshift operation:

• implementing a more efficient multiplication than repeated adding
• implementing division algorithms
• implementing an algorithm for exponentiation of integers by other integers
• bitwise algorithms e.g. "how many one bits in this integer"
• fast multiplication and division by powers of 2 including indexing arrays of integer types (which tend to have sizes of a power of 2 of bytes).
• sending and receiving data on serial lines.
• manipulating bit fields within larger types.
• extracting portions of a combined type and aligning them into new types (Raffzahn)
• manipulating the fields of a software floating point implementation (e.g. aligning the mantissa for addition and normalising the same after any arithmetic operation) (Tommy)
• Accessing the digits in packed BCD formats (i.e. two digits per byte) (Raffzahn)
• Aligning the decimal point in fixed point arithmetic (davidbak)
• cryptography (forest, tofro)
• Aligning rasterised packed bitmaps when blitting them to screen memory (user3570736)

These are just off the top of my head. I'm sure you'll get many answers that include other uses for bit shifts.

I'm not asking what are the use of bitshift operators, but the reason why they were included back then

As I hope you can see from the list, even "back then" bit shift operations were regarded as extremely useful. In particular, it would be hard to write an efficient software multiplication routine without bit shifts.

Answer 2

Then you haven't done any embedded work, or anything to do with comms or protocols.

If you're working with embedded code, you need a way to get values into specific bits in a register. This is true even for the base processor, but especially so for microcontrollers which have extra registers to control the I/O, and for data going to and from devices such as ADCs and DACs. Bitwise operations are essential here, including bit shifting.

For an example of where this is important, I've recently been working with an ADC where the top 3 bits of its 24-bit register specify which of the 8 channels to convert. How would you turn a channel number (0-7) into the appropriate bits in this register, or vice versa, without a bitshift? You could use integer multiplies and divides, but that would be stupidly wasteful given the time those instructions take. (And under the surface, those instructions are using bitshifts themelves anyway!) Technically you could also use a case statement or lookup for each channel number, but that doesn't scale well - don't try using a 16-billion-term case statement to extract individual colours from a 24-bit RGB value!

In the same way, comms protocols regularly pack data into individual bits, especially in packet headers. Again, you need a way to get a number from a variable into any arbitrary group of bits in your protocol bytes, or vice versa. And the same problem has the same solution - you need bitshifting.

Answer 3

In the days before floating point hardware there was fixed-point integer arithmetic! Bit shift instructions were used to implement the "scaling factor" - specifically, to adjust it when you multiplied (or divided) numbers and then had to rescale the number to achieve the desired precision. (Or when adding and subtracting if the operands had different scale factors.)

---

... and now a small break for a fun anecdote:

My first professional programming job involved working on a Honeywell 716 minicomputer. 16-bit word size. It had hardware floating point but it was very slow. It had left shift and right shift instructions but the shift amount was an immediate (4-bit) value in the instruction - there was no instruction or addressing mode where that value was in a register. I was doing a bunch of fixed point arithmetic for signal processing on inputs that had a large dynamic range. There was no single scaling factor I could use for a certain multiply because whatever scaling factor I picked would either overflow for large inputs or lose all precision for small inputs. So ... I computed the necessary scaling factor from the input values and poked it directly into the shift instruction I was about to execute! (Couldn't use a jump table to the correct shift instruction or duplicate code blocks: I was also under a tight memory budget; those 716s only had 32Kwords of memory total.)

First job and I had to break all the rules. Just graduated college and to get approval for that design and code I had to convince the top staff engineer so he could go to the Navy and get their approval.

Answer 4

Along with the many uses of bitshifting (multiplying and dividing by powers of 2, bitmasks, etc.), bitshifting is also very cheap to implement: a simple implementation uses one multiplexer per bit to logical shift for each direction. Adding arithmetic shift is easy too: arithmetic left shift is identical to logical left shift, while arithmetic right shift only requires filling in shifted bits with the MSB.

Designers of old CPUs like the Z80 and MOS 6502 could afford to put in a little bit of extra logic, while hardware multiplication was significantly more resource-intensive and thus expensive. For example only the last 8-bit CPUs had hardware multiplication (notably Motorola 6809, the soon released 16-bit Motorola 68000 had multiplication instructions as well).

Here's a straightforward 3 bit logical left shifter (only 3 8-bit multiplexers are needed):

Answer 5

The fundamental unit of digital information is the bit. Bytes, words, pages, blocks, sectors, tracks, and what have you are all made up of bits. Just about everything that can be done with information can be built up from operations on bits.

Since at least as far back as the 1940s, numbers in computers have usually been represented as sets of bits. Thus the number 23 might be represented as [16, 4, 2, 1]. This is economical both for representation and manipulation.

Just about every processor has special operators for sensing and acting on the sign bit. I'm thinking about instructions like "transfer on minus". If you combine this with instructions for rotating or shifting bits in a register, you can build up just about any complex operation imaginable. The more common operations, like adding two numbers, are going to have instructions, even in a RISC processor. The less common operations are going to be done by bit manipulation.

@JeremyP has an excellent list of bit operations in his answer. It's only a partial list. I'll add telephone line management. If you have a bunch of telephone lines, it might be fairly easy to supply a processor with a set of bits, one bit for each line, where a one bit means, "on hook status has changed".

You can do just about anything, one little bit at a time.