RFC: Brute force bitwise addition

This is a discussion on RFC: Brute force bitwise addition within the C Programming forums, part of the General Programming Boards category; Just for fun, I decided to try to implement addition on a purely bitwise level. I came up with this: ...

  1. #1
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141

    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.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  2. #2
    Registered User
    Join Date
    Jun 2007
    Posts
    6
    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

  3. #3
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,474
    Loop var I'd do the int - for speed
    And probably - loop till CHAR_BIT not 8
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #4
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    Quote Originally Posted by XayC View Post
    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.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,237
    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.
    Last edited by brewbuck; 07-20-2007 at 12:05 PM.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Quote Originally Posted by brewbuck View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 07:52 PM
  2. 2d array Brute force test
    By grimuth in forum C++ Programming
    Replies: 5
    Last Post: 04-08-2010, 10:01 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Replies: 2
    Last Post: 03-21-2004, 07:21 PM
  5. Help : Brute Force String KeyGen
    By Tangy in forum C++ Programming
    Replies: 11
    Last Post: 03-11-2002, 08:01 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21