Performing arithmetic operations in binary using only bitwise operators

Question

Possible Duplicate:
How can I multiply and divide using only bit shifting and adding?

I have to write functions to perform binary subtraction, multiplication, and division without using any arithmetic operators except for loop control. I've only written code in Java before now, so I'm having a hard time wrapping my head around this.

Starting with subtraction, I need to write a function with prototype

int bsub(int x, int y)

I know I need to convert y to two's complement in order to make it negative and add it to x, but I only know how to do this by using one's complement ~ operator and adding 1, but I can't use the + operator.

The badd function was provided, and I will be able to implement it in bsub if I can figure out how to make y a negative number. The code for badd is shown below. Thanks in advance for any tips.

int badd(int x,int y){

int i;

char sum;
char car_in=0;
char car_out;
char a,b;

unsigned int mask=0x00000001;
int result=0;

for(i=0;i<32;i++){

  a=(x&mask)!=0;
  b=(y&mask)!=0;
  car_out=car_in & (a|b) |a&b;
  sum=a^b^car_in;

  if(sum) {
     result|=mask;
  }

  if(i!=31) {
     car_in=car_out;
  } else {
     if(car_in!=car_out) {
        printf("Overflow occurred\n");
     }
  }

  mask<<=1;
  }

 return result;
  }

Solution

Well, subtracting in bitwise operations without the + or - operators is slightly tricky, but can be done. You have the basic idea with the complement, but without using + it becomes slightly tricky.

You can do it by first setting up addition with bit-wise only, then using that, you can do subtraction. Which is used for the complement, So the code looks like this:

int badd(int n1, int n2){
    int carry, sum;
    carry = (n1 & n2) << 1; // Find bits that are used for carry
    sum = n1 ^ n2; // Add each bit, discard carry.
    if (sum & carry) // If bits match, add current sum and carry.
        return badd(sum, carry);
    else
        return sum ^ carry; // Return the sum.
}

int bsub(int n1, int n2){
    // Add two's complement and return.
    return badd(n1, badd(~n2, 1));
}

And then if we use the above code in an example:

int main(){
printf("%d\n", bsub(53, 17));
return 0;
}

Which ends up returning 36. And that is how subtraction works with bitwise only operations.

Afterwards multiplication and division get more complicated, but can be done; for those two operations, use shifts along with addition and/or subtraction to get the job done. You may also want to read this question and this article on how to do it.

Comments

[Maarten Bodewes]

Eh, you don't have + but you do have ~ and badd , so what's missing exactly?

[Maarten Bodewes]

@DonRoby No telling answers, Don.

[LulzCow]

Haha well I guess this should have been fairly obvious to me. I can just use badd to add 1 and ~y, and then use it again to add x to the new value of y. I still don't know how to go about implementing the multiplication or division functions.

[Maarten Bodewes]

Eli, how did you learn to do multiplication?

[LulzCow]

Do you mean the by-hand method learned in elementary school? I could do something similar with the shift operator and a for loop I think, but I'm not quite sure how to begin thinking about it.

[Maarten Bodewes]

You used the shift operator in elementary school? Darn, I'm envious :) I had to explain to the teacher how to use the MSX computers we finally got there.

[Alexey Frunze]

^ in C does XOR, not exponentiation or left shifting. In your pseudo code carry never changes. I'd advise debugging this pseudo code.

[martincho]

You'r right. I've made some corrections.

[vxs8122]

Curious, why use if ( sum & carry ) instead of just if ( carry )?