Класс для чисел в сбалансированной троичной системе счисления

Сбалансированная троичная система счисления (Balanced ternary, статьи по-русски не нашёл) стала известна европейцам со времён книги Штифеля "Arithmetica Integra" (1544 г.).

О ней пишут Кеплер, Колсон, Лесли, Коши и ряд других исследователей, некоторые из которых видят корни системы даже в древних Ведах.

Суть в том, что эта троичная система счисления использует сбалансированное представление целых чисел со знаком, в котором цифры имеют значения -1, 0 и 1, в отличие от стандартных 0, 1 и 2. Таким образом, все целые числа могут быть представлены без использования отдельного знака "минус", а значение первой ненулевой цифры числа имеет знак самого числа.

Если классические двоичные числа с цифрами 0 и 1 обеспечивают простейшую позиционную систему счисления для натуральных чисел и служат логической базой нашей вычислительной техники, то Balanced ternary обеспечивает простейшую автономную ("нестандартную") позиционную систему счисления для целых чисел.

Успешные разработки ЭВМ на основе троичной логики были выполнены в СССР, но дальнейшего развития не получили. А возможно, все наши беды и проистекают от применения бинарности там, где нужна Троица :)

В разных источниках используются разные глифы для представления трёх цифр в сбалансированной троичной системе. Мы ограничимся стандартными и понятными "-", "0" и "+".

Далее показан класс BalancedTernary, содержащий основные операторы для работы с целыми числами в сбалансированной троичной системе и пример его применения. Программа выполнялась в консоли актуальной сборки Visual Studio 2019.

#include <iostream>
#include <string>
#include <climits>
using namespace std;

class BalancedTernary {
protected:
 string value;

 int charToInt(char c) const {
  if (c == '0') return 0;
  return 44 - c;
 }

 string inverse (string s) const {
  for (int i = 0; i < s.length(); ++i) {
   if (s[i] == '+') s[i] = '-';
   else if (s[i] == '-') s[i] = '+';
  }
  return s;
 }

public:
 BalancedTernary() { value = "0"; }

 BalancedTernary(string s) { value = string(s.rbegin(), s.rend()); }

 BalancedTernary(long long n) {
  if (n == 0) { value = "0"; return;  }
  bool neg = n < 0;
  if (neg) n = -n;
  value = "";
  while (n != 0) {
   int r = n % 3;
   if (r == 0) value += "0";
   else if (r == 1) value += "+";
   else {
    value += "-";
    n++;
   }
   n /= 3;
  }
  if (neg) value = inverse(value);
 }

 BalancedTernary(const BalancedTernary& n) {
  value = n.value;
 }

 BalancedTernary operator+ (BalancedTernary n) const {
  n += *this;
  return n;
 }

 BalancedTernary & operator+= (const BalancedTernary& n) {
  const char* add = "0+-0+-0";
  const char* carry = "--000++";
  int lastNonZero = 0;
  char c = '0';
  for (int i = 0; i < value.length() || i < n.value.length(); ++i) {
   char a = i < value.length() ? value[i] : '0';
   char b = i < n.value.length() ? n.value[i] : '0';
   int sum = charToInt(a) + charToInt(b) + charToInt(c) + 3;
   c = carry[sum];
   if (i < value.length()) value[i] = add[sum];
   else value += add[sum];
   if (add[sum] != '0') lastNonZero = i;
  }
  if (c != '0') value += c;
  else //Убрать лидирующие нули
   value = value.substr(0, lastNonZero + 1);
  return *this;
 }

 BalancedTernary operator- () const {
  BalancedTernary result;
  result.value = inverse(value);
  return result;
 }

 BalancedTernary operator- (const BalancedTernary& n) const {
  return operator + (-n);
 }

 BalancedTernary & operator-= (const BalancedTernary& n) {
  return operator += (-n);
 }

 BalancedTernary operator* (BalancedTernary n) const {
  n *= *this;
  return n;
 }

 BalancedTernary & operator*= (const BalancedTernary& n) {
  BalancedTernary pos = *this;
  BalancedTernary neg = -pos; //Копия, чтобы не было повторного "-"
  value = "0";
  for (int i = 0; i < n.value.length(); ++i) {
   if (n.value[i] == '+') operator+=(pos);
   else if (n.value[i] == '-') operator+=(neg);
   pos.value = '0' + pos.value;
   neg.value = '0' + neg.value;
  }
  return *this;
 }

 friend ostream & operator<< (ostream& out, const BalancedTernary& n) {
  out << n.toString();
  return out;
 }

 string toString() const {
  return string(value.rbegin(), value.rend());
 }

 long long toInt() const {
  long long result = 0;
  for (long long i = 0, pow = 1; i < value.length(); ++i, pow *= 3)
   result += pow * charToInt(value[i]);
  return result;
 }

 bool tryToInt(long long& out) const {
  long long result = 0;
  bool ok = true;
  for (long long i = 0, pow = 1; i < value.length() && ok; ++i, pow *= 3) {
   if (value[i] == '+') {
    ok &= LLONG_MAX - pow >= result; //Очистить ok при переполнении
    result += pow;
   }
   else if (value[i] == '-') {
    ok &= LLONG_MIN + pow <= result; //Очистить ok при переполнении
    result -= pow;
   }
  }
  if (ok) out = result;
  return ok;
 }
}; //Класс BalancedTernary

int main() {
 //Создаём 3 числа разными способами
 BalancedTernary a ("++-");  //11
 BalancedTernary b (-4);
 BalancedTernary c ("+-0"); //6

 cout << "a = " << a << " = " << a.toInt() << endl;
 cout << "b = " << b << " = " << b.toInt() << endl;
 cout << "c = " << c << " = " << c.toInt() << endl;

 //Делаем вычисления
 BalancedTernary d = a * (b - c); 
 cout << "a * (b - c) = " << d << " = " << d.toInt() << endl;

 //Тестируем переполнение
 BalancedTernary e ("+++++++++++++++++++++++++++++++++++++++++");
 long long n;
 if (e.tryToInt(n)) cout << "e = " << e << " = " << n << endl;
 else cout << "e = " << e << " overflow for type long long" << endl;

 return 0;
}

03.10.2021, 15:10 [728 просмотров]