Multiplication.cpp

#include <iostream>
#include <deque>

using namespace std;

typedef int8_t i8;
typedef int16_t i16;

deque<int> int2arr(i8 a);
deque<int> int2arr(i16 a);
i16 arr2int(const deque<int> &arr);
deque<int> toAdditional(deque<int> value);
int add(deque<int> &a, const deque<int> &b);
std::ostream &operator<<(std::ostream &os, const deque<int> &value);

void Robertson(i8 a, i8 b);
void Boot(i8 a, i8 b);
void ModBoot(i8 a, i8 b);
void Leman(i8 a, i8 b);

int main() {
  i8 a = -20;
  i8 b = 25;

  Robertson(a, b);
  Boot(a, b);
  ModBoot(a, b);
  Leman(a, b);

  return 0;
}

std::ostream &operator<<(std::ostream &os, const deque<int> &value) {
  for (const auto &item : value) os << item;
  return os;
}

deque<int> int2arr(i8 a) {
  deque<int> result;

  for (int i = 0; i < 8; i++) {
    result.push_front(int(a & 1u));
    a = a >> 1u;
  }

  return result;
}

deque<int> int2arr(i16 a) {
  deque<int> result;

  for (int i = 0; i < 16; i++) {
    result.push_front(a & 1u);
    a = a >> 1;
  }

  return result;
}

int add(deque<int> &a, const deque<int> &b) {
  deque<int> result(8, 0);
  int carry = 0;

  for (int i = 7; i >= 0; i--) {
    int current = carry + a[i] + b[i];
    result[i] = current % 2;
    carry = current / 2;
  }

  a = result;

  return carry;
}

deque<int> toAdditional(deque<int> value) {
  for (int &i : value) {
    i = (i == 1) ? 0 : 1;
  }

  deque<int> one(8, 0);
  one[one.size() - 1] = 1;
  add(value, one);

  return value;
}

i16 arr2int(const deque<int> &arr) {
  i16 result = 0;
  for (int i = 0; i < 16; i++) {
    result = result | i16(arr[i]);
    if (i != 15) result = result << 1;
  }
  return result;
}

void Robertson(i8 a, i8 b) {
  auto aBin = int2arr(a);
  auto bBin = int2arr(b);

  cout << "------------ Алгоритм Робертсона ------------" << endl << endl;

  cout << "a = " << int(a) << ";   " << "aBin = " << aBin << endl;
  cout << "b = " << int(b) << ";   " << "bBin = " << bBin << endl;

  deque<int> result(8, 0);

  cout << "\nСЧП     \tB2СЧП   \tB0\tОп-я\n";
  for (int i = 0; i < bBin.size() - 1; i++) {
    int carry = 0;
    cout << result << "\t" << bBin << "\t" << bBin.back();

    if (bBin.back() == 1) {
      cout << "\t+\n";
      carry = add(result, aBin);
      cout << aBin << "\n" << result << "\t" << bBin << "\t\t" << "->\n";
    } else {
      cout << "\t->\n";
    }

    bBin.pop_back();
    bBin.push_front(result.back());
    result.pop_back();
    if (carry > 0)
      result.push_front(1);
    else
      result.push_front(result.front());
  }

  if (bBin.back() == 1) {
    cout << result << "\t" << bBin << "\t" << bBin.back() << "\t-\n" << toAdditional(aBin) << "\n";
    add(result, toAdditional(aBin));
  }

  cout << result << "\t" << bBin << "\t\t->\n";
  bBin.pop_back();
  bBin.push_front(result.back());
  result.pop_back();
  result.push_front(result.front());

  cout << result << "\t" << bBin << endl;

  result.insert(result.end(), bBin.begin(), bBin.end());

  if (result == int2arr(i16(a * b))) {
    cout << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cout << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
  } else {
    cerr << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cerr << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
    system("pause");
  }
}

void Boot(i8 a, i8 b) {
  auto aBin = int2arr(a);
  auto bBin = int2arr(b);

  cout << "--------------- Алгоритм Бута ---------------" << endl << endl;

  cout << "a = " << int(a) << ";   " << "aBin = " << aBin << endl;
  cout << "b = " << int(b) << ";   " << "bBin = " << bBin << endl;

  cout << "\nСЧП     \tB2СЧП   \tBi-1  Bi\tОп-я\n";
  int last = 0;
  deque<int> result(8, 0);

  for (int i = 0; i < bBin.size(); i++) {
    cout << result << "\t" << bBin << "\t" << last << "  ->  " << bBin.back() << "\t";
    if (last == 0 && bBin.back() == 1) {
      cout << "+\n" << toAdditional(aBin) << "\n";
      add(result, toAdditional(aBin));
    } else if (last == 1 && bBin.back() == 0) {
      cout << "-\n" << aBin << "\n";
      add(result, aBin);
    } else {
      cout << "->\n";
    }

    last = bBin.back();

    bBin.pop_back();
    bBin.push_front(result.back());
    result.pop_back();
    result.push_front(result.front());
  }
  cout << result << "\t" << bBin << endl;

  result.insert(result.end(), bBin.begin(), bBin.end());

  if (result == int2arr(i16(a * b))) {
    cout << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cout << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
  } else {
    cerr << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cerr << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
    system("pause");
  }
}

void ModBoot(i8 a, i8 b) {
  auto aBin = int2arr(a);
  auto bBin = int2arr(b);

  cout << "------- Модифицированный Алгоритм Бута ------" << endl << endl;

  cout << "a = " << int(a) << ";   " << "aBin = " << aBin << endl;
  cout << "b = " << int(b) << ";   " << "bBin = " << bBin << endl;

  cout << "\nСЧП     \tB2СЧП   \tBi+1  Bi  Bi-1\tМод\tОп-я\n";

  int last = 0;
  deque<int> result(8, 0);

  for (int i = 0; i < bBin.size() / 2; i++) {
    cout << result << "\t" << bBin << "\t" << bBin[bBin.size() - 2] << "     " << bBin.back() << "     " << last
         << "\t";

    if ((bBin[bBin.size() - 2] == 0 && bBin.back() == 0 && last == 1) ||
        (bBin[bBin.size() - 2] == 0 && bBin.back() == 1 && last == 0)) {
      cout << "1\t+A\n" << aBin << "\n";
      add(result, aBin);
    } else if ((bBin[bBin.size() - 2] == 1 && bBin.back() == 0 && last == 1) ||
               (bBin[bBin.size() - 2] == 1 && bBin.back() == 1 && last == 0)) {
      cout << "|1\t-A\n" << toAdditional(aBin) << "\n";
      add(result, toAdditional(aBin));
    } else if (bBin[bBin.size() - 2] == 0 && bBin.back() == 1 && last == 1) {
      cout << "2\t+2A\n";
      auto temp = aBin;
      temp.pop_front();
      temp.push_back(0);
      cout << temp << "\n";
      add(result, aBin);
      add(result, aBin);
    } else if (bBin[bBin.size() - 2] == 1 && bBin.back() == 0 && last == 0) {
      cout << "|2\t-2A\n";
      auto temp = toAdditional(aBin);
      temp.pop_front();
      temp.push_back(0);
      cout << temp << "\n";
      add(result, toAdditional(aBin));
      add(result, toAdditional(aBin));
    } else {
      cout << "|2\n";
    }

    last = bBin[bBin.size() - 2];

    cout << result << "\t" << bBin << "\t\t\t\t->->\n";
    bBin.pop_back();
    bBin.push_front(result.back());
    result.pop_back();
    result.push_front(result.front());

    bBin.pop_back();
    bBin.push_front(result.back());
    result.pop_back();
    result.push_front(result.front());
  }
  cout << result << "\t" << bBin << endl;

  result.insert(result.end(), bBin.begin(), bBin.end());

  if (result == int2arr(i16(a * b))) {
    cout << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cout << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
  } else {
    cerr << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cerr << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
    system("pause");
  }
}

void Leman(i8 a, i8 b) {
  auto aBin = int2arr(a);
  auto bBin = int2arr(b);

  cout << "--------------- Алгоритм Лемана -------------" << endl << endl;

  cout << "a = " << int(a) << ";   " << "aBin = " << aBin << endl;
  cout << "b = " << int(b) << ";   " << "bBin = " << bBin << endl;

  deque<int> result(8, 0);
  bool last_d = false;
  bool last_b = false;

  cout << "\nСЧП     \tB2СЧП   \tBi-1\tBi^Bi-1   Di   Si   Оп-я\n";

  for (int i = 0; i < bBin.size(); i++) {
    int d = int((bool(bBin.back()) ^ last_b) * !last_d);
    int s = -1 * d * bBin[bBin.size() - 2] + 1 * d * !bool(bBin[bBin.size() - 2]);

    cout << result << "\t" << bBin << "\t" << last_b << "\t" << (bool(bBin.back()) ^ last_b) << "\t  " << d << "    "
         << s << "   ";
    if (s == -1) {
      cout << "-\n" << toAdditional(aBin) << "\n";
      add(result, toAdditional(aBin));
    } else if (s == 1) {
      cout << " +\n" << aBin << "\n";
      add(result, aBin);
    } else {
      cout << "\n";
    }

    last_d = bool(d);
    last_b = bool(bBin.back());

    cout << result << "\t" << bBin << "\t\t\t\t    ->\n";

    bBin.pop_back();
    bBin.push_front(result.back());
    result.pop_back();
    result.push_front(result.front());
  }
  cout << result << "\t" << bBin << endl;

  result.insert(result.end(), bBin.begin(), bBin.end());

  if (result == int2arr(i16(a * b))) {
    cout << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cout << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
  } else {
    cerr << "\nРезультат:         " << result << " = " << arr2int(result) << endl;
    cerr << "Верный результат:  " << int2arr(i16(a * b)) << " = " << i16(a * b) << endl << endl;
    system("pause");
  }
}