Thread: RFC: Brute force bitwise addition

Just for fun, I decided to try to implement addition on a purely bitwise level. I came up with this:

Code:

void main(void)
{
	unsigned char num1 = 19;
	unsigned char num2 = 6;
	unsigned char sum = 0;
	unsigned char oldcarry = 0;
	unsigned char place = 1;
	unsigned char insertshift = 7;
	unsigned char x;

	for (x = 0; x < 8; x++)
	{
		unsigned char bit1 = place & num1;
		unsigned char bit2 = place & num2;
		unsigned char bitsum = place & (bit1 ^ bit2);
		unsigned char newcarry = 0;

		sum >>= 1;

		if (bit1 & bit2)
		{
			newcarry = place << 1;
		}
		
		if (oldcarry)
		{
			if (bitsum & oldcarry)
			{
				newcarry = place << 1;
			}

			bitsum = place & (bitsum ^ oldcarry);
		}

		sum |= bitsum << insertshift;
		oldcarry = newcarry;
		place <<= 1;
		insertshift -= 1;
	}
}

This seems to work, num1 and num2 are added and the result is stored in sum. It just seems really cumbersome to me, particularly the way in which carries are handled.

I know it's not commented, but I think the variable names are descriptive enough to show what's going on.

I guess I'm just looking for any improvements or suggestions. I don't do a lot of bitwise work, and I wanted the practice for a project I'm working on.

Loop var I'd do the int - for speed
And probably - loop till CHAR_BIT not 8

Originally Posted by XayC

I've made some changes to your code:

Code:

#include <stdio.h>

int main(void)
{
	unsigned char num1 = 19;
	unsigned char num2 = 6;
	unsigned char sum = 0;
	unsigned char place = 1;
	unsigned char x;

	unsigned char carry = 0;

	for (x = 0; x < 8; x++)
	{
		unsigned char bit1 = place & num1;
		unsigned char bit2 = place & num2;
		unsigned char bitsum;

		bitsum = ((bit1 ^ bit2)^carry) & place;
		carry = ((bit1 & bit2) | ( bit2 & carry) | (carry & bit1)) & place;
		carry = carry << 1;

		sum |= bitsum;
		place = place << 1;
	}

	printf( "Sum is: %d", sum);
	return 0;
}

While shorter and maybe faster, this implementation can be less intuitive. Actually the code:

Code:

bitsum = ((bit1 ^ bit2)^carry) & place;
carry = ((bit1 & bit2) | ( bit2 & carry) | (carry & bit1)) & place;

is the logical function of a full adder.
I hope this can help.
Regards, Xay

I knew someone would bite at the void main. This code is going on a PIC chip, which is a freestanding environment. The int main rule doesn't apply there, void main is the defined entry point. (When you assume... etc...)

I hadn't even thought to look at adder logic, for some reason. I'll have to work through your suggestions tonight and see how it works. Thanks.

How about:

Code:

unsigned int add(unsigned int a, unsigned int b)
{
   unsigned int carry = 0;
   unsigned int mask = 1;
   unsigned int result = 0;

   while(mask)
   {
      result |= (a ^ b ^ carry) & mask;
      carry = ((a & b) | (a & carry) | (b & carry)) & mask ? (mask << 1) : 0;
      mask <<= 1;
   }
   return result;
}

EDIT: XayC got it first.

Originally Posted by brewbuck

How about:

Code:

unsigned int add(unsigned int a, unsigned int b)
{
   unsigned int carry = 0;
   unsigned int mask = 1;
   unsigned int result = 0;

   while(mask)
   {
      result |= (a ^ b ^ carry) & mask;
      carry = ((a & b) | (a & carry) | (b & carry)) & mask ? (mask << 1) : 0;
      mask <<= 1;
   }
   return result;
}

EDIT: XayC got it first.

Nah I'd say you win, brewbuck. The other code posted uses x++ in the for loop, which I'd consider cheating since it is addition you're emulating to begin with.