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

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

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

@talis · 14.08.2011, 20:58

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

@diagon · 14.08.2011, 21:02

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

long long.

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

@adamo86 · 14.08.2011, 21:05 **[ТС]**

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

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

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

@talis · 14.08.2011, 21:07

Сообщение от 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 · 14.08.2011, 21:09

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

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

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

@adamo86 · 14.08.2011, 21:13 **[ТС]**

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

return a[i] < b[i];

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

@talis · 14.08.2011, 21:22

Это значит "вернуть результат операции 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 · 14.08.2011, 21:24 **[ТС]**

Сообщение от 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 · 14.08.2011, 21:26

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

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

@silentnuke · 14.08.2011, 21:28

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

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

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

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

@talis · 14.08.2011, 21:29

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

@diagon · 14.08.2011, 21:30

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

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

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

@silentnuke · 14.08.2011, 21:35

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

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

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

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

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

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

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

@talis · 14.08.2011, 21:37

Сообщение от 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 байт.

@silentnuke · 14.08.2011, 21:39

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

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

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

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

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

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

я знаю, что в С изначально его не было.
ну а в С++ bool есть)
давайте будем вспоминать чего ещё где не было?)
хотя ладно, у каждого свои предпочтения, не будем спорить.

@talis · 14.08.2011, 21:40

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

ну это ветка С++

Да ладно!

Сообщение от текст_наверху_этой_страницы

Форум программистов и сисадминов > Форум программистов > C/C++ > С/С++ для начинающих

@diagon · 14.08.2011, 21:45

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

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

Тьфу...
Но на каком-то компиляторе он действительно 4 байта весил.

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

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

Ну так в стиле strcmp. -1 : меньше, 0 : равно, 1 : больше. Что бы не писать много функций для сравнения.

@talis · 14.08.2011, 21:54

diagon, strcmp, тогда уж, возвращает не -1 и не +1, а число < 0 и число > 0, соответственно. Выглядит это примерно так:

C

int strcmp( char *str1, char *str2 )
{
   int difference, i;
   for( i = 0; str1[i] != 0 && str2[i] != 0; i++ )
   {
      difference = str1[i] - str2[i];
      if( difference != 0 )
         return difference;
   }
 
   return str1[i] - str2[i];
}

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

C

int strcmp( char *str1, char *str2 )
{
   int difference;
   while( *str1 != 0 && *str2 != 0 )
   {
      difference = *str1 - *str2;
      if( difference != 0 )
         return difference;
 
      str1++;
      str2++;
   }
 
   return *str1 - *str2;
}

Впрочем, согласитесь, это всё далеко от длинной арифметики, о которй спрашивал ТС

@diagon · 14.08.2011, 21:55

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

Выглядит это примерно так:

Необязательно, может возвращать что угодно =)
В strcmp не имеет значение длина строк, поэтому можно просто возвращать их разность. А в случае с длинными числами 10 больше 9, к примеру. Поэтому проще всего возвращать константу...

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

@silentnuke Android Programmer 139 / 140 / 10 Регистрация: 08.12.2010 Сообщений: 421
	14.08.2011, 21:39	16
	Сообщение от talis Зачем? 1 = меньше, 0 = не меньше, -1 = наверное всё-таки меньше В любом случае, перепишите под себя Во-первых, в C bool изначально не было, и все программеры старой школы по-вашему "быдлокодеры". Брайан Керниган и Деннис Ритчи в частности. Во-вторых gcc у меня до сих пор пишет error: 'bool' undeclared (first use in this function). Так что вот так вот. Добавлено через 1 минуту Зависит от компилятора. В любом случае, чтобы не напороться на bool из 4-х байт, я бы всегда использовал char - он везде будет 1 байт. я знаю, что в С изначально его не было. ну а в С++ bool есть) давайте будем вспоминать чего ещё где не было?) хотя ладно, у каждого свои предпочтения, не будем спорить. 0

@talis 793 / 545 / 61 Регистрация: 11.05.2010 Сообщений: 1,298 Записей в блоге: 1
	14.08.2011, 21:40	17
	Сообщение от silentnuke ну это ветка С++ Да ладно! Сообщение от текст_наверху_этой_страницы Форум программистов и сисадминов > Форум программистов > C/C++ > С/С++ для начинающих 0

@diagon Higher 1937 / 1203 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	14.08.2011, 21:45	18
	Сообщение от silentnuke да ну, с каких это пор bool 4 байта? http://msdn.microsoft.com/en-us/libr...(v=VS.71).aspx Тьфу... Но на каком-то компиляторе он действительно 4 байта весил. Сообщение от talis Зачем? 1 = меньше, 0 = не меньше, -1 = наверное всё-таки меньше Ну так в стиле strcmp. -1 : меньше, 0 : равно, 1 : больше. Что бы не писать много функций для сравнения. 0

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

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

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

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

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

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

@talis 793 / 545 / 61 Регистрация: 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]. Надеюсь, смог прояснить ситуацию. 1

@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? 0

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

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

	14.08.2011, 21:55

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

@silentnuke Android Programmer 139 / 140 / 10 Регистрация: 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/library/cc953fe1(v=VS.71).aspx 0

@talis 793 / 545 / 61 Регистрация: 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 байт. 0

@diagon Higher 1937 / 1203 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	14.08.2011, 21:55	20
	Сообщение от talis Выглядит это примерно так: Необязательно, может возвращать что угодно =) В strcmp не имеет значение длина строк, поэтому можно просто возвращать их разность. А в случае с длинными числами 10 больше 9, к примеру. Поэтому проще всего возвращать константу... 0