Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.83
adamo86
2 / 2 / 0
Регистрация: 10.04.2011
Сообщений: 185
14.08.2011, 20:56     Работа с длинными числами #1
Мне нужно прочитать из файла 22-х значные целые числа для количественного сравнения. int и long int не сохраняют полную длину числа. Какой тип можно использовать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.08.2011, 20:56     Работа с длинными числами
Посмотрите здесь:

Работа с числами C++
C++ Действия над многорозряднымии числами(очень длинными)
Работа с числами в с++ C++
C++ работа с числами
Работа с числами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 20:58     Работа с длинными числами #2
adamo86, есть long long. Если не поместится, и нужно только количественное сравнение (больше/меньше) - читайте как строки и сравнивайте руками.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 не берет. А "Длинная арифметика" что это такое? Где можно про это почитать?
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 21:07     Работа с длинными числами #5
Цитата Сообщение от diagon Посмотреть сообщение
Там чуть больше 19 разрядов
Длинная арифметика в помощь.
Ну вот - пришли к "ручками" Набросал быстро:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// проверяет, что 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
Higher
 Аватар для diagon
1920 / 1186 / 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];
Объясните пожалуйста этот код - что он значит?
talis
 Аватар для talis
789 / 541 / 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
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 21:26     Работа с длинными числами #10
char имеет размер в 1 байт. одного байта хватает, чтобы хранить 0 или 1 - больше не требуется :-)

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

Добавлено через 38 секунд
просто байт - минимальный адресуемый участок памяти, функция не может вернуть бит
оО, a bool чем тогда не устроил?
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 21:29     Работа с длинными числами #12
silentnuke, просто привычка. bool-то тоже 1 байт
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.08.2011, 21:30     Работа с длинными числами #13
Цитата Сообщение от silentnuke Посмотреть сообщение
оО, a bool чем тогда не устроил?
Там же 4 байта.
И по-хорошему функция должна возвращать -1, 0, 1 как strcmp.
silentnuke
Android Programmer
137 / 138 / 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
 Аватар для talis
789 / 541 / 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 байт.
silentnuke
Android Programmer
137 / 138 / 5
Регистрация: 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 есть)
давайте будем вспоминать чего ещё где не было?)
хотя ладно, у каждого свои предпочтения, не будем спорить.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 21:40     Работа с длинными числами #17
Цитата Сообщение от silentnuke Посмотреть сообщение
ну это ветка С++
Да ладно!

Цитата Сообщение от текст_наверху_этой_страницы
Форум программистов и сисадминов > Форум программистов > C/C++ > С/С++ для начинающих
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 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 : больше. Что бы не писать много функций для сравнения.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
14.08.2011, 21:54     Работа с длинными числами #19
diagon, strcmp, тогда уж, возвращает не -1 и не +1, а число < 0 и число > 0, соответственно. Выглядит это примерно так:

C
1
2
3
4
5
6
7
8
9
10
11
12
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
Впрочем, согласитесь, это всё далеко от длинной арифметики, о которй спрашивал ТС
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2011, 21:55     Работа с длинными числами
Еще ссылки по теме:

C++ Длинная арифметика. Класс работы с длинными числами.
C++ Операции с длинными числами - неправильно выводится результат
C++ Функция с++ (работа с длинными числами - вывод результата в файл)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.08.2011, 21:55     Работа с длинными числами #20
Цитата Сообщение от talis Посмотреть сообщение
Выглядит это примерно так:
Необязательно, может возвращать что угодно =)
В strcmp не имеет значение длина строк, поэтому можно просто возвращать их разность. А в случае с длинными числами 10 больше 9, к примеру. Поэтому проще всего возвращать константу...
Yandex
Объявления
14.08.2011, 21:55     Работа с длинными числами
Ответ Создать тему
Опции темы

Текущее время: 05:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru