# Implementing a shifter with only multiplexers

This is my homework question, I would appreciate any hints to help me get started.

A shifter is used to shift a string of 0's and 1's to the left or right by a fixed number of positions. The vacated positions(s) is/are filled by 0. For example, if 0011 is shifted left by one position the result is 0110; if 0011 is shifted right by one position the result is 0001.

Two control signals, S1 and S0, are used to specify the various actions, as given below.

S1 = 0 and S0 = 0: No change, that is, pass input string to output

S1 = 0 and S0 = 0: Shift right one bit position

S1 = 1 and S0 = 0: Shift right two bit positions

S1 = 1 and S0 = 1: Shift left one bit position

Using a number of appropriate multiplexers without any additional logic gate, implement a shifter that accepts a 4-bit string ABCD, and generates the required 4-bit string WXYZ depending on the control signals S1 and S0. Complemented literals are not available. You must label your multiplexers, inputs and outputs clearly.

I researched online about the shifting operation and found out that it actually coincide with arithmetic operations, i.e., so "shift right one bit position" is actually division by 2, and "shift left one bit position" is multiplication by 2. However, I have no idea what "shift right two bit" means, is it division by 5? I tested with 1111 binary code (15) and the result is 0011 (3).

So basically since the shifting operations is just arithmetic operations, should I use the multiplexers to implement the latter? Yet I don't know how to go about it with only two control signals S1 and S0. Do I need 4 multiplexers since the output is 4 bits?

• Homework questions are generally frowned upon in StackExchange. If you do want some help, though, then adding what your research so far has shown, what seems to be the specific stumbling block, and what you see as possible solutions and how, would help get the question perceived a bit more favorably. – Anindo Ghosh Feb 16 '13 at 7:35
• Anindo is right - it's usually a good idea to show what you have tried already, or elaborate on the specific bits you are stuck with. – Oli Glaser Feb 16 '13 at 8:34
• Hi, I made an edit. Sorry for the thoughtless action on my part. – uohzxela Feb 16 '13 at 16:45
• I think you have an error in your post. You seem to specify two different outputs for the same combination of inputs. – Peter Green Dec 5 '15 at 4:32

This isn't a direct answer to your homework, but a response to your analysis of what shifting means numerically.

Yes, shifting a binary number left is a multiplication by 2. In general, shifting a number left by one digit multiplies it by the number base. That is because each digit to the left has a weight of the number base times higher. In decimal, shifting left one digit multiplies the number by ten, in binary by two.

No, shifting right by two does not divide by 5. By the same logic as above, shifting right one digit divides the number by the number base. In binary, this means it gets divided by 2. Shifting two bits right divides by 4. The reason you are not seeing this in you example is because you lost some of the digits.

You started with 1111 binary and shifted it right by two bits. This yields 11.11 binary. Add the weights from each of the digits and you get

  2**1 + 2**0 + 2**-1 + 2**-2
=    2 +    1 +    .5 +   .25
= 3.75

Which is exactly 15/4 as expected. The problem is that you ignored the fraction digits and were therefore only left with 3. In this case, that happened to look like the shift divided by 5.

If you do a integer shift, then shifting by one bit right really does

trunc(N / 2)

where N is the original number and TRUNC simply sets all fraction bits to 0 (truncates them). Note that trunc(15/2) does equal 3.