128bit — Как получить входное 128-битное целое число без знака в переполнении стека
Я новичок в C ++. Я хочу взять беззнаковое 128-битное целое число с помощью scanf и распечатать его с помощью printf. Поскольку я новичок в c ++, я знаю только эти два метода для ввода вывода. Кто-нибудь может мне помочь?
Решение
Вы можете использовать boost, но этот набор библиотек должен быть установлен самостоятельно:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
int main()
{
using namespace boost::multiprecision;
uint128_t v = 0;
std::cin >> v; // read
std::cout << v << std::endl; // write
return 0;
}
Другие решения
Если вы хотите обойтись без повышения, вы можете сохранить значение в два uint64_t как так:
std::string input;
std::cin >> input;
uint64_t high = 0, low = 0, tmp;
for(char c : input)
{
high *= 10;
tmp = low * 10;
if(tmp / 10 != low)
{
high += ((low >> 32) * 10 + ((low & 0xf) * 10 >> 32)) >> 32;
}
low = tmp;
tmp = low + c - '0';
high += tmp < low;
low = tmp;
}
Печатание тогда, однако, становится более уродливым:
std::vector<uint64_t> v;
while(high | low)
{
uint64_t const pow10 = 100000000;
uint64_t const mod = (((uint64_t)1 << 32) % pow10) * (((uint64_t)1 << 32) % pow10) % pow10;
tmp = high % pow10;
uint64_t temp = tmp * mod % pow10 + low % pow10;
v.push_back((tmp * mod + low) % pow10);
low = low / pow10 + tmp * 184467440737 + tmp * /*0*/9551616 / pow10 + (temp >= pow10);
high /= pow10;
}
std::vector<uint64_t>::reverse_iterator i = v.rbegin();
while(i != v.rend() && *i == 0)
{
++i;
}
if(i == v.rend())
{
std::cout << 0;
}
else
{
std::cout << *i << std::setfill('0');
for(++i; i != v.rend(); ++i)
{
std::cout << std::setw(8) << *i;
}
}
Выше решение работает до (в том числе)
340282366920938463463374516198409551615
= 0x ffff ffff ffff ffff ffff ad06 1410 beff
Выше есть ошибка.
Примечание: pow10 можно варьировать, тогда нужно настроить некоторые другие константы, e. г. pow10 = 10:
low = low / pow10 + tmp * 1844674407370955161 + tmp * 6 / pow10 + (temp >= pow10);
а также
std::cout << std::setw(1) << *i; // setw also can be dropped in this case
Увеличение приводит к уменьшению максимального числа, для которого печать все еще работает правильно, уменьшение увеличивает максимум. С pow10 = 10 максимум
340282366920938463463374607431768211425
= ffff ffff ffff ffff ffff ffff ffff ffe1
Я не знаю, откуда возникла ошибка для самых высоких чисел, возможно, из-за некоторого непредвиденного переполнения. Любые предложения приветствуются, тогда я улучшу алгоритм. До тех пор я бы уменьшил pow10 до 10 и ввел специальную обработку для самых больших 30 ошибочных чисел:
std::string const specialValues[0] = { /*...*/ };
if(high == 0xffffffffffffffff && low > 0xffffffffffffffe1)
{
std::cout << specialValues[low - 0xffffffffffffffe2];
}
else
{
/* ... */
}
Поэтому, по крайней мере, мы можем правильно обрабатывать все действительные 128-битные значения.