Сложение вычитание переполнение C++

В С++ нет прямого аналога addc. Для выполнения длинного сложения на чистом С++ можно поступить следующими способами

1. В качестве разряда при сложении использовать максимальный целый тип. Отлавливать переполнение путем дополнительной проверки: если сумма получилась меньше одного (любого) из слагаемых, то перенос в следующий разряд равен 1.

   Допустим, нам надо работать с 256-битными целыми на 64-битной платформе (максимальный целый тип - std::uint64_t). Тогда этот вариант может выглядеть так

   using Number64 = std::uint64_t [4]; // 256 значащих бит
   void add(const Number64 &lhs, const Number64 &rhs, Number64 &res)
   {
     std::uint64_t c;
     res[0] = lhs[0] + rhs[0]; c = res[0] < lhs[0];
     res[1] = lhs[1] + rhs[1] + c; c = c ? res[1] <= lhs[1] : res[1] < lhs[1];
     res[2] = lhs[2] + rhs[2] + c; c = c ? res[2] <= lhs[2] : res[2] < lhs[2];
     res[3] = lhs[3] + rhs[3] + c;    
   }
   

   И GCC и MSVC, кстати, догадываются использовать adc при трансляции этого кода для выполнения самого сложения. А вот того, что это adc и следующий перенос уже сгенерировало они не учитывают.

2. В качестве разряда при сложении использовать целый тип, который меньше максимального (половина максимального). Для выполнения сложения приводить разряды к максимальному целому типу. В таком случае перенос получается в явном виде.

   В тех же условиях этот вариант может выглядеть так

   using Number32 = std::uint32_t [8]; // 256 значащих бит
   void add(const Number32 &lhs, const Number32 &rhs, Number32 &res)
   {
     std::uint64_t c;
     res[0] = c = (std::uint64_t) lhs[0] + rhs[0]; 
     res[1] = c = (std::uint64_t) lhs[1] + rhs[1] + (c >> 32);
     res[2] = c = (std::uint64_t) lhs[2] + rhs[2] + (c >> 32);
     res[3] = c = (std::uint64_t) lhs[3] + rhs[3] + (c >> 32);
     res[4] = c = (std::uint64_t) lhs[4] + rhs[4] + (c >> 32);
     res[5] = c = (std::uint64_t) lhs[5] + rhs[5] + (c >> 32);
     res[6] = c = (std::uint64_t) lhs[6] + rhs[6] + (c >> 32);
     res[7] = (std::uint64_t) lhs[7] + rhs[7] + (c >> 32);
   }
   

3. Второй вариант можно заставить вести себя менее "расточительно" в операции сложения: хранить разряды в максимальном целом типе, но при этом сделать старший бит каждого разряда неиспользуемым. То есть, например, каждое std::uint64_t слово будет хранить только 63 полезных бита. А каждый старший бит будет неиспользуемым: он зарезервирован именно для того, чтобы туда попадал перенос. При этом для представления 256-битного значения понадобится 5 std::uint64_t слов, а не 4

   using Number63 = std::uint64_t [5]; // 320 бит, 315 значащих
   void add(const Number63 &lhs, const Number63 &rhs, Number63 &res)
   {
     res[0] = lhs[0] + rhs[0];
     res[1] = lhs[1] + rhs[1] + (res[0] >> 63); res[0] &= 0x7FFFFFFFFFFFFFFF;
     res[2] = lhs[2] + rhs[2] + (res[1] >> 63); res[1] &= 0x7FFFFFFFFFFFFFFF;
     res[3] = lhs[3] + rhs[3] + (res[2] >> 63); res[2] &= 0x7FFFFFFFFFFFFFFF;
     res[4] = lhs[4] + rhs[4] + (res[3] >> 63); res[3] &= 0x7FFFFFFFFFFFFFFF;
     res[4] &= 0x7FFFFFFFFFFFFFFF;
   }
   

   Но большого смысла в таком представлении с "дырками" в последовательности битов я не вижу. Оно также затруднит реализацию других операцией.

До тех пор пока используются только нативно поддерживаемые аппаратной платформой типы (то есть типы вплоть до std::uint64_t на 64-битной платформе), первый вариант представляется наиболее эффективным. Однако, если компилятор предоставляет эмулированную поддержку расширенных целых типов (например, поддержка __uint128_t в GCC на 64-битных платформах) и компилятор умеет хорошо оптимизировать операции с такими типами, то второй вариант, использующий __uint128_t в качестве "максимального" типа, вполне сможет составить конкуренцию первому.