Atoi() для типа int128_t
Как я могу использовать argv значения с поддержкой int128_t? Я знаю о atoi() и семействе функций, выставленных <cstdlib>, но каким-то образом я не могу найти его для целочисленного значения фиксированной ширины int128_t. Это может быть из-за того, что этот type не поддерживается стандартом c или С++, но есть ли способ заставить этот код работать?
#include <iostream>
int main(int argc, char **argv) {
__int128_t value = atoint128_t(argv[1]);
}
Почти все опубликованные ответы достаточно хороши для меня, но я выбираю ту, которая является решением для моего текущего кода, поэтому также смотрим на другие.
Ответы
Ответ 1
Вот реализация С++:
#include <string>
#include <stdexcept>
__int128_t atoint128_t(std::string const & in)
{
__int128_t res = 0;
size_t i = 0;
bool sign = false;
if (in[i] == '-')
{
++i;
sign = true;
}
if (in[i] == '+')
{
++i;
}
for (; i < in.size(); ++i)
{
const char c = in[i];
if (not std::isdigit(c))
throw std::runtime_error(std::string("Non-numeric character: ") + c)
res *= 10;
res += c - '0';
}
if (sign)
{
res *= -1;
}
return res;
}
int main()
{
__int128_t a = atoint128_t("170141183460469231731687303715884105727");
}
Если вы хотите протестировать его, тогда есть оператор потока здесь.
Производительность
Я провел несколько тестов производительности. Я генерирую 100 000 случайных чисел, равномерно распределенных во всей поддержке __int128_t. Затем я конвертировал каждый из них в 2000 раз. Все эти (200 000 000) конверсий завершены в течение ~ 12 секунд.
Используя этот код:
#include <iostream>
#include <string>
#include <random>
#include <vector>
#include <chrono>
int main()
{
std::mt19937 gen(0);
std::uniform_int_distribution<> num(0, 9);
std::uniform_int_distribution<> len(1, 38);
std::uniform_int_distribution<> sign(0, 1);
std::vector<std::string> str;
for (int i = 0; i < 100000; ++i)
{
std::string s;
int l = len(gen);
if (sign(gen))
s += '-';
for (int u = 0; u < l; ++u)
s += std::to_string(num(gen));
str.emplace_back(s);
}
namespace sc = std::chrono;
auto start = sc::duration_cast<sc::microseconds>(sc::high_resolution_clock::now().time_since_epoch()).count();
__int128_t b = 0;
for (int u = 0; u < 200; ++u)
{
for (int i = 0; i < str.size(); ++i)
{
__int128_t a = atoint128_t(str[i]);
b += a;
}
}
auto time = sc::duration_cast<sc::microseconds>(sc::high_resolution_clock::now().time_since_epoch()).count() - start;
std::cout << time / 1000000. << 's' << std::endl;
}
Ответ 2
Добавление здесь "не столь наивной" реализации в чистом C, это все еще просто:
#include <stdio.h>
#include <inttypes.h>
__int128 atoi128(const char *s)
{
while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '+') ++s;
int sign = 1;
if (*s == '-')
{
++s;
sign = -1;
}
size_t digits = 0;
while (s[digits] >= '0' && s[digits] <= '9') ++digits;
char scratch[digits];
for (size_t i = 0; i < digits; ++i) scratch[i] = s[i] - '0';
size_t scanstart = 0;
__int128 result = 0;
__int128 mask = 1;
while (scanstart < digits)
{
if (scratch[digits-1] & 1) result |= mask;
mask <<= 1;
for (size_t i = digits-1; i > scanstart; --i)
{
scratch[i] >>= 1;
if (scratch[i-1] & 1) scratch[i] |= 8;
}
scratch[scanstart] >>= 1;
while (scanstart < digits && !scratch[scanstart]) ++scanstart;
for (size_t i = scanstart; i < digits; ++i)
{
if (scratch[i] > 7) scratch[i] -= 3;
}
}
return result * sign;
}
int main(int argc, char **argv)
{
if (argc > 1)
{
__int128 x = atoi128(argv[1]);
printf("%" PRIi64 "\n", (int64_t)x); // just for demo with smaller numbers
}
}
Он читает число бит за битом, используя сдвинутое место для хранения BCD, см. Double dabble для алгоритма (здесь он отменяется). Это намного эффективнее, чем много умножений на 10 вообще. *)
Это зависит от VLA, без них вы можете заменить
char scratch[digits];
с
char *scratch = malloc(digits);
if (!scratch) return 0;
и добавьте
free(scratch);
в конце функции.
Конечно, приведенный выше код имеет те же ограничения, что и исходный atoi() (например, он будет генерировать "случайный" мусор при переполнении и не имеет возможности проверить это). Если вам нужны strtol() -стальные гарантии и проверку ошибок, расширьте его самостоятельно (не большая проблема, просто работайте).
*) Конечно, реализация двойной привязки в C всегда страдает от того факта, что вы не можете использовать "аппаратные носители", поэтому необходимы дополнительные операции маскировки и тестирования бит. С другой стороны, "наивное" умножение на 10 может быть очень эффективным, если платформа предоставляет инструкции умножения с шириной "закрыть" вашему целевому типу. Поэтому на вашей типичной платформе x86_64 (которая имеет инструкции для умножения 64-битных целых чисел) этот код, вероятно, намного медленнее, чем наивный десятичный метод. Но он значительно масштабируется для действительно огромных целых чисел (которые вы бы реализовали, например, используя массивы uintmax_t).
Ответ 3
Есть ли способ заставить этот код работать?
"Как насчет реализации собственного atoint128_t?" @Marian
Нельзя катить собственный atoint128_t().
Точки для рассмотрения.
-
Существует 0 или 1 более представимое отрицательное значение, чем положительные. Накопление значения с использованием отрицательных чисел дает больший диапазон.
-
Переполнение не определено для atoi(). Возможно, укажите ограниченное значение и установите errno? Обнаружение потенциала OF предотвращает UB.
-
__int128_t константы нуждаются в тщательном формировании кода.
-
Как обрабатывать необычный ввод? atoi() довольно свободен и имеет смысл много лет назад для скорости/размера, но в то же время в UB обычно требуется меньшее количество UB. Кандидаты: "", " ", "-", "z", "+123", "999..many...999", "the min int128", "locale_specific_space" + " 123" или даже нестроковые NULL.
-
Код для выполнения atoi() и atoint128_t() может варьироваться только по типу, диапазону и именам. Алгоритм тот же.
#if 1
#define int_t __int128_t
#define int_MAX (((__int128_t)0x7FFFFFFFFFFFFFFF << 64) + 0xFFFFFFFFFFFFFFFF)
#define int_MIN (-1 - int_MAX)
#define int_atoi atoint128_t
#else
#define int_t int
#define int_MAX INT_MAX
#define int_MIN INT_MIN
#define int_atoi int_atoi
#endif
Пример кода: При необходимости. Использует функции C99 или более поздние negative/positive и %.
int_t int_atoi(const char *s) {
if (s == NULL) { // could omit this test
errno = EINVAL;
return 0;
}
while (isspace((unsigned char ) *s)) { // skip same leading white space like atoi()
s++;
}
char sign = *s; // remember if the sign was `-` for later
if (sign == '-' || sign == '+') {
s++;
}
int_t sum = 0;
while (isdigit((unsigned char)*s)) {
int digit = *s - '0';
if ((sum > int_MIN/10) || (sum == int_MIN/10 && digit <= -(int_MIN%10))) {
sum = sum * 10 - digit; // accumulate on the - side
} else {
sum = int_MIN;
errno = ERANGE;
break; // overflow
}
s++;
}
if (sign != '-') {
if (sum < -int_MAX) {
sum = int_MAX;
errno = ERANGE;
} else {
sum = -sum; // Make positive
}
}
return sum;
}
Как @Lundin прокомментировал отсутствие обнаружения переполнения и т.д. Моделирование строки → int128 после strtol() - лучшая идея.
Для простоты рассмотрим __128_t strto__128_base10(const char *s, char *endptr);
Этот ответ на все готовые обрабатывает переполнение и флаги errno как strtol(). Просто нужно несколько изменений:
bool digit_found = false;
while (isdigit((unsigned char)*s)) {
digit_found = true;
// delete the `break`
// On overflow, continue looping to get to the end of the digits.
// break;
// after the `while()` loop:
if (!digit_found) { // optional test
errno = EINVAL;
}
if (endptr) {
*endptr = digit_found ? s : original_s;
}
Полная функциональность long int strtol(const char *nptr, char **endptr, int base); также будет обрабатывать другие базы со специальным кодом, если base - 0 или 16. @chqrlie
Ответ 4
Вот простой способ реализации этого:
__int128_t atoint128_t(const char *s)
{
const char *p = s;
__int128_t val = 0;
if (*p == '-' || *p == '+') {
p++;
}
while (*p >= '0' && *p <= '9') {
val = (10 * val) + (*p - '0');
p++;
}
if (*s == '-') val = val * -1;
return val;
}
Этот код проверяет каждый символ, чтобы увидеть, является ли он цифрой (с необязательным ведущим + или -), и если это умножит текущий результат на 10 и добавит значение, связанное с этой цифрой. Затем он инвертирует знак, если это необходимо.
Обратите внимание, что эта реализация не проверяет переполнение, что согласуется с поведением atoi.
EDIT:
Пересмотренная реализация, которая охватывает случай int128_MIN путем добавления или вычитания значения каждой цифры на основе знака и пропущенного пробела.
int myatoi(const char *s)
{
const char *p = s;
int neg = 0, val = 0;
while ((*p == '\n') || (*p == '\t') || (*p == ' ') ||
(*p == '\f') || (*p == '\r') || (*p == '\v')) {
p++;
}
if ((*p == '-') || (*p == '+')) {
if (*p == '-') {
neg = 1;
}
p++;
}
while (*p >= '0' && *p <= '9') {
if (neg) {
val = (10 * val) - (*p - '0');
} else {
val = (10 * val) + (*p - '0');
}
p++;
}
return val;
}
Ответ 5
Стандарт C не поддерживает поддержку 128-битных целых чисел.
Тем не менее, они обычно поддерживаются современными компиляторами: gcc и clang поддерживают типы __int128_t и __uint128_t, но на удивление все еще сохраняют intmax_t и uintmax_t ограниченными до 64 бит.
Помимо основных арифметических операторов поддержка этих больших целых чисел, особенно в библиотеке C, не поддерживается: no scanf() или printf() спецификаторы преобразования и т.д.
Вот реализация strtoi128(), strtou128() и atoi128(), которая соответствует спецификациям C Standard atoi(), strtol() и strtoul().
#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Change these typedefs for your local flavor of 128-bit integer types */
typedef __int128_t i128;
typedef __uint128_t u128;
static int strdigit__(char c) {
/* This is ASCII / UTF-8 specific, would not work for EBCDIC */
return (c >= '0' && c <= '9') ? c - '0'
: (c >= 'a' && c <= 'z') ? c - 'a' + 10
: (c >= 'A' && c <= 'Z') ? c - 'A' + 10
: 255;
}
static u128 strtou128__(const char *p, char **endp, int base) {
u128 v = 0;
int digit;
if (base == 0) { /* handle octal and hexadecimal syntax */
base = 10;
if (*p == '0') {
base = 8;
if ((p[1] == 'x' || p[1] == 'X') && strdigit__(p[2]) < 16) {
p += 2;
base = 16;
}
}
}
if (base < 2 || base > 36) {
errno = EINVAL;
} else
if ((digit = strdigit__(*p)) < base) {
v = digit;
/* convert to unsigned 128 bit with overflow control */
while ((digit = strdigit__(*++p)) < base) {
u128 v0 = v;
v = v * base + digit;
if (v < v0) {
v = ~(u128)0;
errno = ERANGE;
}
}
if (endp) {
*endp = (char *)p;
}
}
return v;
}
u128 strtou128(const char *p, char **endp, int base) {
if (endp) {
*endp = (char *)p;
}
while (isspace((unsigned char)*p)) {
p++;
}
if (*p == '-') {
p++;
return -strtou128__(p, endp, base);
} else {
if (*p == '+')
p++;
return strtou128__(p, endp, base);
}
}
i128 strtoi128(const char *p, char **endp, int base) {
u128 v;
if (endp) {
*endp = (char *)p;
}
while (isspace((unsigned char)*p)) {
p++;
}
if (*p == '-') {
p++;
v = strtou128__(p, endp, base);
if (v >= (u128)1 << 127) {
if (v > (u128)1 << 127)
errno = ERANGE;
return -(i128)(((u128)1 << 127) - 1) - 1;
}
return -(i128)v;
} else {
if (*p == '+')
p++;
v = strtou128__(p, endp, base);
if (v >= (u128)1 << 127) {
errno = ERANGE;
return (i128)(((u128)1 << 127) - 1);
}
return (i128)v;
}
}
i128 atoi128(const char *p) {
return strtoi128(p, (char**)NULL, 10);
}
char *utoa128(char *dest, u128 v, int base) {
char buf[129];
char *p = buf + 128;
const char *digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
*p = '\0';
if (base >= 2 && base <= 36) {
while (v > (unsigned)base - 1) {
*--p = digits[v % base];
v /= base;
}
*--p = digits[v];
}
return strcpy(dest, p);
}
char *itoa128(char *buf, i128 v, int base) {
char *p = buf;
u128 uv = (u128)v;
if (v < 0) {
*p++ = '-';
uv = -uv;
}
if (base == 10)
utoa128(p, uv, 10);
else
if (base == 16)
utoa128(p, uv, 16);
else
utoa128(p, uv, base);
return buf;
}
static char *perrno(char *buf, int err) {
switch (err) {
case EINVAL:
return strcpy(buf, "EINVAL");
case ERANGE:
return strcpy(buf, "ERANGE");
default:
sprintf(buf, "%d", err);
return buf;
}
}
int main(int argc, char *argv[]) {
char buf[130];
char xbuf[130];
char ebuf[20];
char *p1, *p2;
i128 v, v1;
u128 v2;
int i;
for (i = 1; i < argc; i++) {
printf("%s:\n", argv[i]);
errno = 0;
v = atoi128(argv[i]);
perrno(ebuf, errno);
printf(" atoi128(): %s 0x%s errno=%s\n",
itoa128(buf, v, 10), utoa128(xbuf, v, 16), ebuf);
errno = 0;
v1 = strtoi128(argv[i], &p1, 0);
perrno(ebuf, errno);
printf(" strtoi128(): %s 0x%s endptr:\"%s\" errno=%s\n",
itoa128(buf, v1, 10), utoa128(xbuf, v1, 16), p1, ebuf);
errno = 0;
v2 = strtou128(argv[i], &p2, 0);
perrno(ebuf, errno);
printf(" strtou128(): %s 0x%s endptr:\"%s\" errno=%s\n",
utoa128(buf, v2, 10), utoa128(xbuf, v2, 16), p2, ebuf);
}
return 0;
}
