CODEWITHSUNDEEP
c++
user259584
user259584

Reputation: 65

addition using bitwise operators

so the idea of my class is to take a string of numbers const char* s = "123456654987" i took each couple of number and stored them in one byte num[0] = 12 , num[1] = 34 and so on ..... this is how i did it 

unsigned char* num;
 num = new unsigned char[ strlen(s)/2 + strlen(s)%2];
    if(strlen(s)%2 == 1)
    num[0] = s[0]-'0';
        unsigned int i;
        int j=strlen(s)%2;
        for(i=strlen(s)%2;i<strlen(s);i+=2)
        {
                        int left = s[i] - '0';
                        int right = s[i+1] - '0';
                        num[j] = left << 4 ;
                        num[j] |= right;
                        j++;
        }

for example s[0] = 12 is represented in memory as 00010010 not as 00000110 but now that i'm trying to overload the += operator i didn't know how to proceed my best try was this but even i know that is not going to work 

int i,sum,carry=0;
    for(i=this->size-1;i>=0;i--)
    {
        sum = ((num[i]  ^ rhs.num[i])  ^ carry);
        carry = ((num[i] & rhs.num[i]) | (num[i] & carry)) | (rhs.num[i] & carry);
        num[i] = sum;
    }

anyhelp guys

Upvotes: 0

Views: 128

Answers (1)

6502
6502

Reputation: 114461

You will need to do the addition one digit (4 bit) at a time because 9+9=18 and 18 won't fit in 4 bits.

x-oring multibit digits however is not the correct operation.. the correct algorithm for sum is something like

int carry = 0;
for(int i=0; i<n; i++) {
    if ((i & 1) == 0) {
        int x = (a[i] & 15) + (b[i] & 15) + carry;
        result[i] = (x & 15);
        carry = x > 15;
    } else {
        int x = (a[i] >> 4) + (b[i] >> 4) + carry;
        result[i] |= (x << 4);
        carry = x > 15;
    }
}

Working in assembler many processors supports detection of an overflow in the lower 4 bits when doing an operation and there are specific instructions to "fix" the result so that it becomes the correct two-digit binary decimal representation (e.g. x86 provides DAA instruction to fix the result of an addition).

Working at the C level however this machinery is not available.

Upvotes: 1

Related Questions