0
$\begingroup$

Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift operators. I'm interested to know what sequence of bitshift operations can reproduce the addition operation.

$\endgroup$
  • 3
    $\begingroup$ This is covered in courses and textbooks on digital logic. A circuit which adds two numbers is known as an adder. $\endgroup$ – Yuval Filmus Feb 5 at 10:28
3
$\begingroup$

This is impossible, a shift does not combine two operands.

$\endgroup$
0
$\begingroup$

You can partly perform an addition, but the practical interest is definitely null.

A logic circuit can be described as a thruth table.

Consider for instance the truth table of a full adder (sum)

a b c | sum=a xor b xor c
0 0 0 | 0
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1

Shifting can somehow be considered as a way to perform a table lookup.

If we build v=4*a+2*b+c and T=0b10010110, we can see that the LSB of T>>v equals the corresponding entry. So, to get only the corresponding bit, we can do

unsigned fulladd_sum(unsigned a,b,c) {
  // note a,b,c must only have their LSB eventually set
  unsigned int as, bs, cs;      
  unsigned int T=0b10010110;
  unsigned int sum;
  as=a<<2; bs=b<<1; cs=c<<0;
  sum = ((T >> as) >> bs) >> cs ;
  return (sum <<31) >> 31 ; // to get rid of useless bits
}

And we have the sum bit. We can do the same for the carry and process this way successive bits.

The only problem, as already spotted, is that we have no way to combine bits and the result will be spread over several variables representing the successive logic weights of the result.

Concerning the operands, we can have normal operands and extract individual bits by shifting and cleaning (with ((op >> i) <<31) >>31 to get the ith bit).

$\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.