4
\$\begingroup\$

I'm a software developer and I understand how arithmetic and logical bitshifts work in principle.

But how do they work on the electrical layer?

I might have a completely wrong imagination;

Let's say we have the binary value 0000 1011 and left shift it by 2.
The outcome is 0010 1100, nothing special.

But how do the bits "jump" to their second neighbors?

Edit: Fixed a slip, where I wrote "right shift" while doing a left shift.

Edit: Added ALU and DIGITAL-LOGIC tags

\$\endgroup\$
  • \$\begingroup\$ You have shifted left by two bits. Shifting right would result in 0000 0010. You might want to clarify your question: are you talking about micro controllers or hard-wired logic? The "jump to their second neighbors" bit is easy. You repeat a single bit-shift as many times as you require. \$\endgroup\$ – Transistor Apr 5 '16 at 9:08
  • 4
    \$\begingroup\$ en.wikipedia.org/wiki/Barrel_shifter \$\endgroup\$ – pjc50 Apr 5 '16 at 9:14
  • \$\begingroup\$ Oh what a careless mistake, my bad. Of course I'm left-shifting. Repeating a specific operation is clear, shifting twice to shift by two is easy. But still, how does the shift itself happens? I've read several times, that shifting is a extreme fast operation and due my lack of engineering knowledge, I don't know why that is the case. \$\endgroup\$ – Sempie Apr 5 '16 at 9:20
  • 1
    \$\begingroup\$ In that case you should learn how a flip-flop works. A shift register is just that - several flip-flops in series. \$\endgroup\$ – Dmitry Grigoryev Apr 5 '16 at 9:43
  • \$\begingroup\$ or try electronics-tutorials.ws/sequential/seq_5.html \$\endgroup\$ – JIm Dearden Apr 5 '16 at 10:46
5
\$\begingroup\$

In computers, arithmetic operations are performed by a specific integrated circuit that is placed inside the microprocessor, and is called "Arithmetic Logic Unit". You can have a look at the Wikipedia article on ALU ( https://en.wikipedia.org/wiki/Arithmetic_logic_unit ). As an example it mentions the 74181 ALU, which is a very simple Arithmetic logic unit, able to perform several types of operations, including the left shift, over 4 bits.

I've attached the logic schema of the 74181 ALU (see below). Inputs are A and B, and result is F. Each number is 4 bits long, so there is A3A2A1A0, B3B2B1B0, and F3F2F1F0. The desired operation is selected with S3S2S1S0:

  • F = A (op) B
  • 'op' is the desired operation.
  • If S = S3S2S1S0 = 1100, then 'op' is left shifting.

This is how left shifting works in the particular case of the 74181:

  • Look at the upper left group of five AND gates and 2 NOR gates.
  • First AND gate is not exactly AND, because it has only one entry: /A0. Therefore its output is /A0.
  • Second and third AND gates have 0 output because S1S0 = 00
  • Fourth AND gate has output /A0*B0, because S2 = 1
  • Fifth AND gate has output /A0*/B0, because S3 = 1
  • First NOR gate has output A0.
  • Second NOR gate has output A0, because /A0*B0 + /A0*/B0 = /A0.

In conclusion, when you have S3S2S1S0 = 1100, the ALU makes F = A + A, which is the same as left shifting.

Simplified schema of the 74181 ALU

\$\endgroup\$
2
\$\begingroup\$

One approach is a parellel in parallel out shift register. The data is loaded into the shift register, then shifted left or right by the desired number of places. The down-side of this is that it can only shift by one bit per clock cycle.

An alternative is a barrel shifter which can shift by an arbitrary number of places in one go.

It's worth realising that shifting need be nothing more than how you wire the input lines to the output lines on a data bus. Wired straight through is no shift. Wire each input line to the output line that is one place to the left is a left shift by 1, and so on.

\$\endgroup\$
1
\$\begingroup\$

Look up something called a shift register. One way to think about these is a chain of flip-flops. Let's say these flip-flops take a snapshot of whatever value is on their input on the low to high transition of the clock, then transfer that snapshot to their output on the next high to low transition of the clock. You connect the output of one flip-flop to the input of the next, etc, then connect them all to the same clock signal.

\$\endgroup\$
0
\$\begingroup\$

Ones and zeros are represented inside the CPU integrated circuit as voltage levels. For example 0 volts is logic zero, and 5 volts is logic one. Logic values are typically held in circuits called "flip-flop"s. A typical CPU chip has millions of flip-flops.

And a typical CPU chip also has millions of electrically-operated switches. So, in order to execute a shift function, the CPU turns on the appropriate switches to send the logic levels over to the NEXT flip-flop (or "bit position") in the register.

Basically all math and logic functions are implemented by simply connecting bit registers in particular ways depending on what you want to do. That is what the CPU chip is designed to do.

\$\endgroup\$
0
\$\begingroup\$

When you rotate the tires on your car how does that happen? Well you take at least two off and swap them yes?

Bit storage be it individual flip-flops or gobzillions of them packed in a ram. Each bit of storage is readable and writeable. otherwise what is the point? A bit shift is nothing more than an operation that takes the tires off, reads the bits out of a register or memory location, and then writes them back in a different location, just like moving one tire from the back to the front, you read it out, then write it back in a different location.

There is no magic in logic, it is all very very simple in concept. zero, one, and, or, not is all that is required to understand. It is just at times a massive amount of and, ors and nots in parallel and/or series.

Some processors shift one bit at a time and in pseudo hdl it is not really different than in software

alu_out[16] = (operand_a[14:0],0)

the 16 bit output is made of the lower 15 bits of the input re-positioned to the upper 15 bits of the output with a zero tacked on in the 0 position.

And that line of code may be in a switch like statement or tree of if then else statements that basically says if alu_operation = left_shift then do this.

And all of that is compiled into logic gates, the ifs and the assignments turn in to and, or, not gates or gates derived from and, or, not. on a massive rats nest.

Some processors have a variable sized shifter that in one operation can rotate or shift however much you want (up to the whole word size obviously, otherwise what is the point) granted that takes a lot more gates, just that one operation each bit of the output for a 16 bit register has a 15, 16, or 17 to one mux depending, just for that one operation.

\$\endgroup\$

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.