Работа с длинными числами - C++

@adamo86 · Регистрация: 10.04.2011

Мне нужно прочитать из файла 22-х значные целые числа для количественного сравнения. int и long int не сохраняют полную длину числа. Какой тип можно использовать?

@talis · Регистрация: 11.05.2010

adamo86, есть long long. Если не поместится, и нужно только количественное сравнение (больше/меньше) - читайте как строки и сравнивайте руками.

@diagon · Регистрация: 02.05.2010

Сообщение от talis

long long.

Там чуть больше 19 разрядов
Длинная арифметика в помощь.

@adamo86 · Регистрация: 10.04.2011

Сообщение от diagon

Там чуть больше 19 разрядов
Длинная арифметика в помощь.

long long не берет. А "Длинная арифметика" что это такое? Где можно про это почитать?

@talis · Регистрация: 11.05.2010

Сообщение от diagon

Там чуть больше 19 разрядов
Длинная арифметика в помощь.

Ну вот - пришли к "ручками"

Набросал быстро:

C

// проверяет, что a меньше b.
char a_less_then_b( char *a, char * b )
{
    unsigned short a_len = strlen( a ),
                   b_len = strlen( b ),
                   i;
 
    if( a_len == b_len )
        for( i = 0; i < a_len; i++ )
           if( a[i] != b[i] )
               return a[i] < b[i];
 
    return a_len < b_len;
}

Она не умеет работать с минусом и требует отсутствия ведущих нулей.

@diagon · Регистрация: 02.05.2010

Сообщение от adamo86

А "Длинная арифметика" что это такое?

Представление числа в виде массива чисел.
Тут алгоритмы есть..
http://e-maxx.ru/algo/big_integer

@adamo86 · Регистрация: 10.04.2011

Сообщение от talis

return a[i] < b[i];

Объясните пожалуйста этот код - что он значит?

@talis · Регистрация: 11.05.2010

Это значит "вернуть результат операции a[i] < b[i]". Представьте, что это арифметическая операция, вроде сложения. return a[i] + b[i] - это уже понятнее

только если у операции "+" результат - сумма левого и правого операнда, то у операции "<" - логическое значение (0 или 1), говорящее о том, что a[i] меньше b[i] (в случае, если оно равно 1) или что a[i] не меньше b[i] (если оно равно 0).

Другими словами, если a[i] меньше b[i], то вернётся 1, если же это не так (a[i] не меньше b[i]), то вернётся 0.

Добавлено через 5 минут
Смысл тут такой: есть два числа:

99999949999
99999969999

Если они имеют разную длину, то очевидно, что большим из них будет число с большей длиной (при условии, что нет лидирующих нулей и без учёта знака минуса). Например, тут очвеидно, что первое число больше второго:

4654684156415213
99999

Если же длина равна, как в первом случае, то нужно слева направо, от старшего разряда к младшему, искать первое различие между числами:

a[0] = 9;
b[0] = 9;
различия нет, идём дальше
a[1] = 9;
b[1] = 9;
различия нет, идём дальше
...
a[6] = 4;
b[6] = 6;
есть различие! если a[6] < b[6], то a < b. Соответственно, return a[i] < b[i].

Надеюсь, смог прояснить ситуацию.

@adamo86 · Регистрация: 10.04.2011

Сообщение от talis

// проверяет, что a меньше b.
char a_less_then_b( char *a, char * b )
{
* * unsigned short a_len = strlen( a ),
* * * * * * * * * *b_len = strlen( b ),
* * * * * * * * * *i;
if( a_len == b_len )
* * * * for( i = 0; i < a_len; i++ )
* * * * * *if( a[i] != b[i] )
* * * * * * * *return a[i] < b[i];
return a_len < b_len;
}

Если a < b, то ответом будет целое значение наверное. Тогда почему функция a_less_then_b типа char?

@talis · Регистрация: 11.05.2010

char имеет размер в 1 байт. одного байта хватает, чтобы хранить 0 или 1 - больше не требуется :-)

Добавлено через 38 секунд
просто байт - минимальный адресуемый участок памяти, функция не может вернуть бит

@silentnuke · Регистрация: 08.12.2010

Сообщение от talis

char имеет размер в 1 байт. одного байта хватает, чтобы хранить 0 или 1 - больше не требуется :-)

Добавлено через 38 секунд
просто байт - минимальный адресуемый участок памяти, функция не может вернуть бит

оО, a bool чем тогда не устроил?

@talis · Регистрация: 11.05.2010

silentnuke, просто привычка. bool-то тоже 1 байт

@diagon · Регистрация: 02.05.2010

Сообщение от silentnuke

оО, a bool чем тогда не устроил?

Там же 4 байта.
И по-хорошему функция должна возвращать -1, 0, 1 как strcmp.

@silentnuke · Регистрация: 08.12.2010

Сообщение от talis

silentnuke, просто привычка. bool-то тоже 1 байт

да, но это в стиле быдлокода.)
ведь bool как раз и создан для этих целей, и куда привычнее увидеть bool, все станет на свои места, а с вашим char придется смотреть реализацию, чтобы понять чтоже оно возвращает. имхо

Добавлено через 3 минуты

Сообщение от diagon

Там же 4 байта.
И по-хорошему функция должна возвращать -1, 0, 1 как strcmp.

да ну, с каких это пор bool 4 байта? http://msdn.microsoft.com/en-us/libr...(v=VS.71).aspx

@talis · Регистрация: 11.05.2010

Сообщение от diagon

И по-хорошему функция должна возвращать -1, 0, 1 как strcmp.

Зачем? 1 = меньше, 0 = не меньше, -1 = наверное всё-таки меньше

В любом случае, перепишите под себя

Сообщение от silentnuke

да, но это в стиле быдлокода.)

Во-первых, в C bool изначально не было, и все программеры старой школы по-вашему "быдлокодеры". Брайан Керниган и Деннис Ритчи в частности. Во-вторых gcc у меня до сих пор пишет error: 'bool' undeclared (first use in this function). Так что вот так вот.

Добавлено через 1 минуту

Сообщение от silentnuke

с каких это пор bool 4 байта?

Сообщение от msdn

Its size is unspecified.

Зависит от компилятора. В любом случае, чтобы не напороться на bool из 4-х байт, я бы всегда использовал char - он везде будет 1 байт.

@talis 791 / 543 / 37 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 20:58 Работа с длинными числами	#2
	adamo86, есть long long. Если не поместится, и нужно только количественное сравнение (больше/меньше) - читайте как строки и сравнивайте руками.

@diagon Higher 1928 / 1194 / 49 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	14.08.2011, 21:02 Работа с длинными числами	#3
	Сообщение от talis long long. Там чуть больше 19 разрядов Длинная арифметика в помощь.

@adamo86 2 / 2 / 0 Регистрация: 10.04.2011 Сообщений: 185
	14.08.2011, 21:05 [ТС] Работа с длинными числами	#4
	Сообщение от diagon Там чуть больше 19 разрядов Длинная арифметика в помощь. long long не берет. А "Длинная арифметика" что это такое? Где можно про это почитать?

@diagon Higher 1928 / 1194 / 49 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	14.08.2011, 21:09 Работа с длинными числами	#6
	Сообщение от adamo86 А "Длинная арифметика" что это такое? Представление числа в виде массива чисел. Тут алгоритмы есть.. http://e-maxx.ru/algo/big_integer

@adamo86 2 / 2 / 0 Регистрация: 10.04.2011 Сообщений: 185
	14.08.2011, 21:13 [ТС] Работа с длинными числами	#7
	Сообщение от talis return a[i] < b[i]; Объясните пожалуйста этот код - что он значит?

@adamo86 2 / 2 / 0 Регистрация: 10.04.2011 Сообщений: 185
		#1
	Работа с длинными числами - C++ 14.08.2011, 20:56. Просмотров 5651. Ответов 24 Метки нет (Все метки) Мне нужно прочитать из файла 22-х значные целые числа для количественного сравнения. int и long int не сохраняют полную длину числа. Какой тип можно использовать?

@talis 791 / 543 / 37 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 21:22 Работа с длинными числами	#8
	Это значит "вернуть результат операции a[i] < b[i]". Представьте, что это арифметическая операция, вроде сложения. return a[i] + b[i] - это уже понятнее только если у операции "+" результат - сумма левого и правого операнда, то у операции "<" - логическое значение (0 или 1), говорящее о том, что a[i] меньше b[i] (в случае, если оно равно 1) или что a[i] не меньше b[i] (если оно равно 0). Другими словами, если a[i] меньше b[i], то вернётся 1, если же это не так (a[i] не меньше b[i]), то вернётся 0. Добавлено через 5 минут Смысл тут такой: есть два числа: 99999949999 99999969999 Если они имеют разную длину, то очевидно, что большим из них будет число с большей длиной (при условии, что нет лидирующих нулей и без учёта знака минуса). Например, тут очвеидно, что первое число больше второго: 4654684156415213 99999 Если же длина равна, как в первом случае, то нужно слева направо, от старшего разряда к младшему, искать первое различие между числами: a[0] = 9; b[0] = 9; различия нет, идём дальше a[1] = 9; b[1] = 9; различия нет, идём дальше ... a[6] = 4; b[6] = 6; есть различие! если a[6] < b[6], то a < b. Соответственно, return a[i] < b[i]. Надеюсь, смог прояснить ситуацию.

@adamo86 2 / 2 / 0 Регистрация: 10.04.2011 Сообщений: 185
	14.08.2011, 21:24 [ТС] Работа с длинными числами	#9
	Сообщение от talis // проверяет, что a меньше b. char a_less_then_b( char a, char b ) { * * unsigned short a_len = strlen( a ), * * * * * * * * * b_len = strlen( b ), * * * * * * * * i; if( a_len == b_len ) * * * for( i = 0; i < a_len; i++ ) * * * * * if( a[i] != b[i] ) * * * * * * *return a[i] < b[i]; return a_len < b_len; } Если a < b, то ответом будет целое значение наверное. Тогда почему функция a_less_then_b типа char?

@talis 791 / 543 / 37 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 21:26 Работа с длинными числами	#10
	char имеет размер в 1 байт. одного байта хватает, чтобы хранить 0 или 1 - больше не требуется :-) Добавлено через 38 секунд просто байт - минимальный адресуемый участок памяти, функция не может вернуть бит

@silentnuke Android Programmer 139 / 140 / 5 Регистрация: 08.12.2010 Сообщений: 421
	14.08.2011, 21:28 Работа с длинными числами	#11
	Сообщение от talis char имеет размер в 1 байт. одного байта хватает, чтобы хранить 0 или 1 - больше не требуется :-) Добавлено через 38 секунд просто байт - минимальный адресуемый участок памяти, функция не может вернуть бит оО, a bool чем тогда не устроил?

@talis 791 / 543 / 37 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 21:29 Работа с длинными числами	#12
	silentnuke, просто привычка. bool-то тоже 1 байт

@diagon Higher 1928 / 1194 / 49 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	14.08.2011, 21:30 Работа с длинными числами	#13
	Сообщение от silentnuke оО, a bool чем тогда не устроил? Там же 4 байта. И по-хорошему функция должна возвращать -1, 0, 1 как strcmp.

@silentnuke Android Programmer 139 / 140 / 5 Регистрация: 08.12.2010 Сообщений: 421
	14.08.2011, 21:35 Работа с длинными числами	#14
	Сообщение от talis silentnuke, просто привычка. bool-то тоже 1 байт да, но это в стиле быдлокода.) ведь bool как раз и создан для этих целей, и куда привычнее увидеть bool, все станет на свои места, а с вашим char придется смотреть реализацию, чтобы понять чтоже оно возвращает. имхо Добавлено через 3 минуты Сообщение от diagon Там же 4 байта. И по-хорошему функция должна возвращать -1, 0, 1 как strcmp. да ну, с каких это пор bool 4 байта? http://msdn.microsoft.com/en-us/libr...(v=VS.71).aspx

@talis 791 / 543 / 37 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 21:37 Работа с длинными числами	#15
	Сообщение от diagon И по-хорошему функция должна возвращать -1, 0, 1 как strcmp. Зачем? 1 = меньше, 0 = не меньше, -1 = наверное всё-таки меньше В любом случае, перепишите под себя Сообщение от silentnuke да, но это в стиле быдлокода.) Во-первых, в C bool изначально не было, и все программеры старой школы по-вашему "быдлокодеры". Брайан Керниган и Деннис Ритчи в частности. Во-вторых gcc у меня до сих пор пишет error: 'bool' undeclared (first use in this function). Так что вот так вот. Добавлено через 1 минуту Сообщение от silentnuke с каких это пор bool 4 байта? Сообщение от msdn Its size is unspecified. Зависит от компилятора. В любом случае, чтобы не напороться на bool из 4-х байт, я бы всегда использовал char - он везде будет 1 байт.

Yandex Объявления	14.08.2011, 21:37 Работа с длинными числами

Опции темы

С++ для начинающих

Работа с длинными числами - C++