How to multiply two binary numbers modulo 2 that are stored as strings

Question

How to multiply two binary numbers modulo 2 that are stored as strings

Example: In the zero position, the highest digit of the binary number is stored. The result is a number consisting of digits {0,1}.

string MulBinary(const string& left, const string &right)
{
    vector<int> res;
    int len = left.length() + right.length() ;
    res.resize(len);
    int k = 0;
    for (int i = right.length()-1 ; i>=0 ; i--)
    {
        for (int j = left.length()-1; j >= 0; j--)
        {
            res[k] ^= ((left[i] - '0') * (right[j] - '0'));
        }
        k++;
    }
    string t;
    for (int i = 0; i < res.size(); i++)
    {
        t.push_back(res[i] + '0');
    }
    return t;
}

But it turns out that it counts incorrectly, that is, the answer does not match what is in the picture.

0

c++строки binary vector xor

Author: ANurbaev, 2020-01-04

Source

1 answers

score 1 · Answer 1

1101x1110=10110110

The standard way to store long numbers is in reverse order, i.e. the element with the number 0 stores the lowest digit. This removes a lot of problems.

Multiplication function by 2 (shift)

string shift(const string& num) {

    return "0" + num;
}

Adding two long binary numbers

string add(const string& left, const string &right) {
    string temp = "";
    string a, b;
    int w = 0,d;
    //а длинное число, b - короткое
    if (left.length() < right.length()) {
        temp = right; a = left; 
    }
    else {
        a = right; temp = left;
    }

    for (int i = 0; i < temp.length(); i++) {
        if (i < a.length()) {
            d = (temp[i] - '0') + (a[i] - '0') + w;
        }
        else {
            d = (temp[i] - '0') + w;
        }
        temp[i] = (char)(d % 2 + '0');
        w = d / 2;
    }
    if (w == 1) { temp = temp + '1'; }

    return temp;

}

The multiplication algorithm. At each step, we shift one multiplier by 1 position and add it to the result.

string MulBinary(const string& left, const string &right)
{
    string temp;
    string a = left;
    if (right[0] == '0') {
        temp = "0";
    }
    else {
        temp = left;
    }
    for (int i = 1; i < right.length(); i++)
    {
        a = shift(a);
        if (right[i] == '1') {
            temp = add(temp, a);
        }


    }

    return temp;
}