CODEWITHSUNDEEP
c++vectorbinarypseudocodemultiplication
Valrok
Valrok

Reputation: 1574

Multiplying two integers given in binary

I'm working on a program that will allow me to multiply/divide/add/subtract binary numbers together. In my program I'm making all integers be represented as vectors of digits.

I've managed to figure out how to do this with addition, however multiplication has got me stumbled and I was wondering if anyone could give me some advice on how to get the pseudo code as a guide for this program.

Thanks in advance!

EDIT: I'm trying to figure out how to create the algorithm for multiplication still to clear things up. Any help on how to figure this algorithm would be appreciated. I usually don't work with C++, so it takes me a bit longer to figure things out with it.

Upvotes: 0

Views: 14239

Answers (5)

withinthemess
withinthemess

Reputation: 1

I made this algorithm that uses a binary addition function that I found on the web in combination with some code that first adjusts "shifts" the numbers before sending them to be added together. It works with the logic that's in this video https://www.youtube.com/watch?v=umqLvHYeGiI

and this is the code:

#include <iostream>
#include <string>

using namespace std;

// This function adds two binary strings and return 
// result as a third string 
string addBinary(string a, string b)
{
    string result = ""; // Initialize result 
    int s = 0;          // Initialize digit sum 
    int flag =0;
    // Traverse both strings starting from last 
    // characters 
    int i = a.size() - 1, j = b.size() - 1;
    
    while (i >= 0 || j >= 0 || s == 1)
    {

        // Computing the sum of the digits from right to left
          //x = (condition) ? (value_if_true) : (value_if_false);
          //add the fire bit of each string to digit sum 
        s += ((i >= 0) ? a[i] - '0' : 0);
        s += ((j >= 0) ? b[j] - '0' : 0);


        // If current digit sum is 1 or 3, add 1 to result 
        //Other wise it will be written as a zero 2%2 + 0 = 0
            //and it will be added to the heading of the string (to the left)
        result = char(s % 2 + '0') + result;

        // Compute carry
        //Not using double so we get either 1 or 0 as a result
        s /= 2;

        // Move to next digits (more to the left)
        i--; j--;
    }
    return result;
}

int main()
{

    string a, b, result= "0"; //Multiplier, multiplicand, and result
    string temp="0";  //Our buffer
    int shifter = 0;  //Shifting counter 

    puts("Enter you binary values");
    cout << "Multiplicand     =  ";
    cin >> a;
    cout<<endl;

    cout << "Multiplier     =   ";
    cin >> b;
    cout << endl;

    //Set a pointer that looks at the multiplier from the bit on the most right 
    int j = b.size() - 1;

   // Loop through the whole string and see if theres any 1's
    while (j >= 0)
    {
        if (b[j] == '1')
        { 
            //Reassigns the original value every loop to delete the old shifting 
            temp = a;


            //We shift by adding zeros to the string of bits
            //If it is not the first iteration it wont add any thing because we did not "shift" yet
            temp.append(shifter, '0');
                
            //Add the shifter buffer bits to the result variable 
            result = addBinary(result, temp);
        }

        //we shifted one place 
        ++shifter; 
        
        //move to the next bit on the left
        j--;
    }


    cout << "Result     = " << result << endl;


    return 0;
}

Upvotes: 0

aStranger
aStranger

Reputation: 249

Just tried something, and this would work if you only multiply unsigned values in binary:

unsigned int multiply(unsigned int left, unsigned int right)
{
    unsigned long long result = 0; //64 bit result

    unsigned int R = right; //32 bit right input
    unsigned int M = left; //32 bit left input

    while (R > 0)
    {
        if (R & 1)
        {// if Least significant bit exists
            result += M; //add by shifted left
        }
        R >>= 1;
        M <<= 1; //next bit
    }

/*-- if you want to check for multiplication overflow: --
    if ((result >> 32) != 0)
    {//if has more than 32 bits
        return -1; //multiplication overflow
    }*/

    return (unsigned int)result;
}

However, that's at the binary level of it... I just you have vector of digits as input

Upvotes: 0

aStranger
aStranger

Reputation: 249

You could also consider the Booth's algorithm if you'd like to multiply: Booth's multiplication algorithm

Upvotes: 3

Luchian Grigore
Luchian Grigore

Reputation: 258568

Long multiplication in pseudocode would look something like:

vector<digit> x;
vector<digit> y;

total = 0;
multiplier = 1;
for i = x->last -> x->first   //start off with the least significant digit of x
   total = total + i * y * multiplier
   multiplier *= 10;

return total

Upvotes: 2

elyashiv
elyashiv

Reputation: 3691

you could try simulating a binary multiplier or any other circuit that is used in a CPU.

Upvotes: 0

Related Questions