Implementation of arithmetic shift in C/C++

Question

Is there a way to implement the Left Arithmetic Shift and Right Arithmetic Shift, using only operations AND, OR, NOT, XOR?

Are you sure [logical shifts](https://stackoverflow.com/q/25206670/11683) are not allowed? — GSerg, Sep 07 '19 at 08:55
Notice that OR and XOR can be expressed in terms of AND and NOT. Hence your question would be equivalent even if OR and XOR were removed. — nielsen, Sep 07 '19 at 10:46
@nielsen basically, all operations can be recreated using only NAND logic) — Miradil Zeynalli, Sep 07 '19 at 11:02

score 2 · Answer 1 · answered Sep 07 '19 at 12:13

In each of the operations AND, OR, NOT, and XOR, each bit in the result is solely a function of the one (OT) or two (AND, OR, XOR) bits in the same position in the operands. In a shift by any amount other than zero, each bit in the result is a function of a bit in a different position in the operand being shifted. Therefore, it is not possible to compute a shift solely from AND, OR, NOT, and XOR.

score 1 · Answer 2 · answered Sep 07 '19 at 09:03

1

Consider a = 0b0011.

Then we have ~a = 0b1100.

We also have a | ~a = 0b1111.

And also a & ~a = 0b0000.

You can manually check all possible combinations of &, ^, ~, and | to see that we can't make anything more than those four binary values. None of which are 0b0110 (what we want from left shift) or 0b0001 (what we want from right shift).

Since we found a number for which it can't be done, then we know in general it can't be done.

answered Sep 07 '19 at 09:03

druckermanly

2,694
15
27

The OP does not mention that constants are not allowed. If constants are allowed we can surely create other values and without having thought it completely through, I am quite sure we can construct shift operators. – nielsen Sep 07 '19 at 10:39
@nielsen: Constants do not perform shifts. If you select which constants to use using operations such as `? :` or control statements such as `if`, then you are not using just AND, OR, NOT, and XOR. – Eric Postpischil Sep 07 '19 at 12:11
@Eric Postpischil You are right, I was thinking more in terms of mathematics, but since the question is tagged `C` we must assume that the AND, OR, NOT and XOR operations are the `C` operations and that we are not allowed to pick out bits and use them as input in other positions (which would make the solution quite trivial since the shift operators really do not involve logic operations). Hence I believe that your answer is the most correct one. – nielsen Sep 07 '19 at 15:19

Miradil Zeynalli · Answer 3 · 2019-09-07T11:04:52.567

-1

IT IS POSSIBLE

Basically, the main logic of shifting is using shifters (barrel shifter and barrel shifter with multiplexers) which in turn can be created using multiplexers. And you can create multiplexers easily using the logical operations that you mentioned. Here is 2-to-1 MUX created with NAND gates: Mux with NAND

edited Sep 07 '19 at 11:04

answered Sep 07 '19 at 10:18

Miradil Zeynalli

423
4
18

Because the question is tagged with [C], it asks about C operations, not about constructing shifts using wires or logic gates. – Eric Postpischil Sep 07 '19 at 12:10
1

Well, if you understand logic behind shifters, it is pretty easy to implement it in any programming language – Miradil Zeynalli Sep 07 '19 at 13:53

Implementation of arithmetic shift in C/C++

3 Answers3