CODEWITHSUNDEEP
operatorsbit-shiftbitwise-operators
Tomek
Tomek

Reputation: 4829

One position right barrel shift using ALU Operators?

I was wondering if there was an efficient way to perform a shift right on an 8 bit binary value using only ALU Operators (NOT, OR, AND, XOR, ADD, SUB) 

Example:

input:  00110101
output: 10011010

I have been able to implement a shift left by just adding the 8 bit binary value with itself since a shift left is equivalent to multiplying by 2. However, I can't think of a way to do this for shift right.

The only method I have come up with so far is to just perform 7 left barrel shifts. Is this the only way?

Upvotes: 3

Views: 2584

Answers (1)

MSalters
MSalters

Reputation: 179907

It's trivial to see that this cannot be done with {AND, OR, XOR, NOT}. For all these operators, outbit[N] depends on inbit1[N] and inbit2[N] only. AND adds a dependency on inbit1[N]..inbit1[0] and inbit2[N]..inbit2[0]. However, in your case you require a dependency on inbit[N+1]. Therefore, it follows that if there is any solution, it must include a SUB.

However, A - B is just A + (-B) which is A + ((B XOR 11111111) +1). Hence, if there was a solution using SUB, it could be rewritten as a solution using ADD and XOR instead. As we've shown, those operators are insufficient. Hence, the set {ADD, OR, XOR, NOT, ADD, SUB} is insufficient too.

Upvotes: 2

Related Questions