0

Пример: В нулевом позиции хранится старший разряд двоичного числа. Результат число состоящая из цифр {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;
}

Но получается, оно считает неправильно, то есть, ответ не совпадает с тем, что на картинке.

введите сюда описание изображения

8
  • В нулевом символе строки хранится нулевой разряд числа? (последняя цифра)
    – becouse
    4 янв 2020 в 14:20
  • И еще. У вас произведение по модулю 2.оно может быть 0 или 1.уточните вопрос.
    – becouse
    4 янв 2020 в 14:23
  • @becouse Да, в [0] старший бит
    – ANurbaev
    4 янв 2020 в 14:37
  • например число 1101 в массиве записано как 1011? Старший бит он крайний левый младший бит крайний правый. У вас путаница в терминологии.
    – becouse
    4 янв 2020 в 14:41
  • @because string a = "1101". Так и записано. a[0] = '1' - старший бит (стоит на краю слева), a[3] = '1' - младший бит.
    – ANurbaev
    4 янв 2020 в 14:51

1 ответ 1

1
  1. 1101х1110=10110110

Стандартный способ хранения длинных чисел: в обратном порядке, т.е. в элементе с номером 0 хранится младший разряд. Это снимает массу проблем.

Функция умножения на 2 (сдвиг)

string shift(const string& num) {

    return "0" + num;
}

Сложение двух длинных двоичных чисел

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;

}

Алгоритм умножения. На каждом шаге сдвигаем один множитель на 1 позицию и прибавляем к результату.

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.