c++ - 以二进制形式给出的两个整数相乘

Question

我正在开发一个允许我将二进制数相乘/除/加/减的程序。在我的程序中，我将所有整数表示为数字向量。

我已经设法弄清楚如何通过加法来做到这一点，但是乘法让我绊倒了，我想知道是否有人可以就如何获取伪代码作为该程序的指南给我一些建议。

提前致谢！

编辑：我试图弄清楚如何创建乘法算法仍然可以解决问题。任何有关如何计算此算法的帮助将不胜感激。我通常不使用 C++，所以我需要更长的时间才能弄清楚它。

Answer 1

如果你想乘法，你也可以考虑布斯算法： 布斯乘法算法

Answer 2

伪代码中的长乘法看起来像：

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

Answer 3

您可以尝试模拟二进制乘法器或 CPU 中使用的任何其他电路。

Answer 4

刚刚尝试了一些东西，如果你只在二进制中乘以无符号值，这将起作用：

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;
}

但是，那是它的二进制级别......我只是你有数字向量作为输入

Answer 5

我制作了这个算法，它使用了我在网上找到的二进制加法函数，并结合了一些代码，这些代码首先调整“移位”数字，然后再将它们相加。它适用于此视频中的逻辑https://www.youtube.com/watch?v=umqLvHYeGiI

这是代码：

#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;
}