Создавайте большие числа по BCD
Я хочу создать код, который поможет мне получить цифры больше, чем MAXINT. Я слышал о том, что я могу использовать Binary Code Decimal, чтобы сделать это, и затем каждые два десятичных числа (преобразованные в BCD) большего числа остаются в char. Но как это сделать? Я должен дать строку в качестве ввода, а затем преобразовать как-то в BCD каждое десятичное число? И как я могу поместить два преобразованных десятичных чисел в один символ? Я новичок в C ++ и не знаю, как я могу это сделать.
Постскриптум Я не хочу использовать библиотеки, которые являются «специальными» для такого рода проблем.
Решение
Оказывается, это на самом деле довольно просто. Как насчет того, чтобы попытаться поднять его на следующий уровень?
Ниже приведена реализация числа BCD с бесконечным (или столько, сколько может вместить в себя) размером. Он поддерживает только положительные целые числа. Я оставлю расширение этого, чтобы поддержать отрицательные числа (или действительные числа) в качестве упражнения.
Перво-наперво: да, мы хотим получить наш номер в виде строки, а затем построить его из этого. Поскольку это всего лишь целое число, это на самом деле довольно легко сделать. В первую очередь мы создаем вспомогательную функцию, которая помогает нам идентифицировать все цифры.
int char_to_int(const char c) {
int ret = c - '0';
if(ret > 9 || ret < 0) throw 1; // for simplicity. Use a class derived from std::exception instead.
return ret;
}
Теперь мы можем попытаться реализовать ввод и вывод для нашего большого числа.
Первая попытка
Имея этого помощника, легко превратить строку в закодированный в BCD буфер. Обычная реализация может выглядеть так:
int main() {
unsigned char bignum[10]; // stores at most 20 BCD digits.
std::memset(bignum, 0, sizeof(bignum));
std::string input;
std::cin >> input;
try {
if (input.size() > 20) throw 1; // Avoid problems with buffer overflow.
for (int i=1;i<=input.size();i++) {
int n = char_to_int(input[input.size()-i]);
bignum[sizeof(bignum) - (i+1)/2] |= n << (i%2)*4; // These are bitwise operations. Google them!
}
}
catch(int) {
std::cout << "ERROR: Invalid input.\n";
return 0; // Exit cleanly.
}
// bignum is now filled. Let's print it to prove.
for (int i=0;i<sizeof(bignum);i++) {
int first_digit = bignum[i] & '\x0F'; // Right side, doesn't need to shift.
int second_digit = (bignum[i] & '\xF0')>>4; // Left side, shifted.
std::cout << first_digit << second_digit;
}
}
Это не очень экономно, однако. Обратите внимание, что мы должны хранить все 20 цифр, даже если наш номер маленький! Что если нам понадобится 1000 цифр? Что если нам понадобится 1000 номеров, которые могут иметь или не иметь эти 1000 цифр? Это также подвержено ошибкам: посмотрите, что мы должны были помнить, чтобы инициализировать массив, и сделать проверку границ перед преобразованием, чтобы избежать переполнения буфера.
Вторая попытка
Мы можем улучшить нашу реализацию, используя std :: vector:
int main() {
std::vector<unsigned char> bignum; // stores any quantity of digits.
std::string input;
std::cin >> input;
try {
// For an odd number of digits we want a trailling zero at the end.
if(input.size()%2) n.num_vec.push_back(char_to_int(input[0]));
for (unsigned i=input.size()%2;i<input.size();i+=2) {
int left = char_to_int(input[i]);
int right = char_to_int(input[i+1]);
n.num_vec.push_back(0);
n.num_vec.back() = left << 4;
n.num_vec.back() |= right;
}
}
catch(int) {
std::cout << "ERROR: Invalid input.\n";
exit(0); // Exit cleanly.
}
// bignum is now filled. Let's print it to prove.
for (unsigned i=0;i<bignum.size();++i) {
// Notice that we inverted this from the previous one! Try to think why.
int first_digit = (bignum[i] & '\xF0')>>4; // Left side, shifted.
int second_digit = bignum[i] & '\x0F'; // Right side, doesn't need to shift.
if(i || first_digit) std::cout << first_digit; // avoid printing trailling 0.
std::cout << second_digit;
}
}
Выглядит хорошо, но это слишком громоздко. В идеале, пользователь bignumber не должен иметь дело с векторными позициями и всем этим mumbo-jumbo. Мы хотим написать код, который ведет себя так:
int main() {
int a;
cin >> a;
cout << a;
}
И это должно просто работать.
Третья попытка
Оказывается, это возможно! Просто поместите bignum в класс с некоторыми полезными операторами:
class bignum {
std::vector<unsigned char> num_vec;
template<typename T>
friend T& operator<<(T& is, bignum& n);
template<typename T>
friend T& operator>>(T& os, bignum& n);
};
// Get input from any object that behaves like an std::istream (i.e.: std::cin)
template<typename T>
T& operator>>(T& is, bignum& n) {
std::string input;
is >> input;
n.num_vec.reserve(input.size());
if(input.size()%2) n.num_vec.push_back(char_to_int(input[0]));
for (unsigned i=input.size()%2;i<input.size();i+=2) {
int left = char_to_int(input[i]);
int right = (i+1) != input.size()?char_to_int(input[i+1]):0; // If odd number of digits, avoid getting garbage.
n.num_vec.push_back(0);
n.num_vec.back() = left << 4;
n.num_vec.back() |= right;
}
return is;
}
// Output to any object that behaves like an std::ostream (i.e.: std::cout)
template<typename T>
T& operator<<(T& os, bignum& n) {
for (unsigned i=0;i<n.num_vec.size();++i) {
int first_digit = (n.num_vec[i] & '\xF0')>>4; // Left side, shifted.
int second_digit = n.num_vec[i] & '\x0F'; // Right side, doesn't need to shift.
if(i || first_digit) os << first_digit; // avoid printing trailling 0.
os << second_digit;
}
return os;
}
Тогда наша основная функция выглядит гораздо более читабельной:
int main() {
bignum a;
try {
std::cin >> a;
}
catch(int) {
std::cout << "ERROR: Invalid input.\n";
return 0; // Exit cleanly.
}
std::cout << a;
}
эпилог
И вот у нас это есть. Конечно, без операторов сложения, умножения и т. Д. Это не очень полезно. Я оставлю их как упражнение. Код, код и еще немного кода, и скоро это будет выглядеть как кусок пирога для вас.
Пожалуйста, не стесняйтесь задавать любые вопросы. Хорошее кодирование!
Другие решения