Long Hand Multiplication In C++

问题:

I am trying to implement Long Hand Multiplication method for 8 bit binary numbers stored in two arrays BeforeDecimal1 and BeforeDecimal2. The problem is I always get the wrong result. I tried to figure out the issue but couldn't do it. Here is the code:

This is a much more refined code then previous one. It is giving me result but the result is not correct.

int i=0,carry=0;

while(true)
{
    if(BeforeDecimal2[i]!=0)
        for(int j=7;j>=0;j--)
        {
            if(s[j]==1 && BeforeDecimal1[j]==1 && carry==0)
            {
                cout<<"Inside first, j= "<<j<<endl;
                carry=1;
                s[j]=0;
            }
            else
                if(s[j]==1 && BeforeDecimal1[j]==0 && carry==1)
                {
                    cout<<"Inside second, j= "<<j<<endl;
                    carry=1;
                    s[j]=0;
                }
                else
                    if(s[j]==0 && BeforeDecimal1[j]==0 && carry==1)
                    {
                        cout<<"Inside third, j= "<<j<<endl;
                        carry=0;
                        s[j]=1;
                    }
                    else
                        if(s[j]==0 && BeforeDecimal1[j]==0 && carry==0)
                        {
                            cout<<"Inside fourth, j= "<<j<<endl;
                            carry=0;
                            s[j]=0;
                        }
                        else
                            if(s[j]==0 && BeforeDecimal1[j]==1 && carry==0)
                            {
                                cout<<"Inside fifth, j= "<<j<<endl;
                                carry=0;
                                s[j]=1;
                            }

                            else
                                if(s[j]==1 && BeforeDecimal1[j]==1 && carry==1)
                                {
                                    //cout<<"Inside fifth, j= "<<j<<endl;
                                    carry=1;
                                    s[j]=1;
                                }
                                else
                                    if(s[j]==1 && BeforeDecimal1[j]==0 && carry==0)
                                    {
                                        //cout<<"Inside fifth, j= "<<j<<endl;
                                        carry=0;
                                        s[j]=1;
                                    }
                                    else
                                        if(s[j]==0 && BeforeDecimal1[j]==1 && carry==1)
                                        {
                                            //cout<<"Inside fifth, j= "<<j<<endl;
                                            carry=1;
                                            s[j]=0;
                                        }

        }

        for(int h=7;h>=0;h--)
        {
            if(h==0)
            {
                BeforeDecimal1[0]=0; // that is inserting zeros from the right
            }
            else
            {
                BeforeDecimal1[h]=BeforeDecimal1[h-1];
                BeforeDecimal1[h-1]=0;
            }

        }
    if(i==3)
        break;

    i++;
}

Regards

回答1:

Maybe it would be easiest to back up and start with 8-bit binary numbers stored as 8-bit binary numbers. Much like when we do decimal multiplication, we start with a number of digits. We take the values of multiplying by those individual digits, and add them together to get the final result. The difference (or one obvious difference) is this since we're working in binary, all our digits represent powers of two, so we can get each intermediate result by simply bit shifting the input.

Since it's binary, we have only two possibilities for each digit: if it's a 0, then we need to add 0 times the other number shifted left the appropriate number of places. Obviously, 0 time whatever is still 0, so we simply do nothing in this case. The other possibility is that we have a 1, in which case we add 1 times the other number shifted left the appropriate number of places.

For example, let's consider something like 17 x 5, or (in binary) 10001 x 101.

     10001
       101
    ------
     10001
 + 1000100
  --------
 = 1010101      

Converting that to something more recognizable, we get 0x55, or 85_d.

In code, that process comes out fairly short and simple. Start with a result of 0. Check whether the least significant bit in one operand is set. If so, add the other operand to the result. Shift the one operand right a bit and the other left a bit, and repeat until the operand you're shifting to the right equals 0:

unsigned short mul(unsigned char input1, unsigned char input2) { 
    unsigned short result = 0;

    while (input2 != 0) {
        if (input2 & 1)
            result += input1;
        input1 <<= 1;
        input2 >>= 1;
    }
    return result;
}

If you want to deal with signed numbers, it's generally easiest to figure up the sign of the result separately, and do the multiplication on the absolute values.

回答2:

You have problem in following lines of code

if(reverse==0)
{
    totalReverse=totalReverse-1;
    reverse=totalReverse;
}

after some iterations of the inner for loop (index j based) the values of reverse goes should goes to negative and when reverse less than 3 then there should be exception thrown.

Are you running this code without exception handling?

回答3:

to me this smells like shift and add. is there a requirement that you may use operations simulating logical gates only?

for your full adder you have 3 inputs s(s[j]), b(BeforeDecimal1[j]), c(carry), and two outputs ns(new s[j]), nc (new carry) the table looks like this

s  b  c ns nc
0  0  0  0  0 handled in v5 clause 4
0  0  1  1  0 handled in v5 clause 3
0  1  0  1  0 handled in v6 clause 5
0  1  1  0  1
1  0  0  1  0
1  0  1  0  1 handled in v5 clause 2
1  1  0  0  1 handled in v5 clause 1
1  1  1  1  1

your code covers only 4 (now 5) of these 8 clauses

to avoid the ugly if-else-if rake i recommend to use temporary result variables (carry and s still valid in the next if clause)

when you analyze the table you could also do (pseudo bool notation)

nc = s && b || s && c || b && c;
ns = s XOR b XOR c;              // there is no XOR in C++: axb = a&&!b || !a&&b

arithmetic notation

nc = (s + b + c) / 2;
ns = (s + b + c) % 2;



// [...]
for(int j=7;j>=0;j--)
{
    // start changed code
    const int sum = s[j] + BeforeDecimal1[j] + carry;
    s[j]=sum % 2;
    carry=sum / 2;
    // end changed code
}
// [...]

here is a nice simulation of your problem Sequential Multiplication

回答4:

Unless your requirement precisely states otherwise, which isn't clear from your question or any of your comments so far, it is not necessary to process arrays of bits. Arrays of bytes are much more efficient in both space and time.

You don't need this exhaustive explosion of cases either. The only special case is where either operand is zero, i.e. a[i]|b[i] == 0, when

result[i] = carry;
carry = 0;

All other cases can be handled by:

result[i] = a[i]*b[i]+carry;
carry = (result[i] >>> 8) & 1;
result[i] &= 0xff;

I don't see much point in the names BeforeDecimal1 and BeforeDecimal2 either.