bigint · Cristi

▶ Aprender bigint (Cristi) paso a paso · explicación de bigint

Otras versiones: One line · Multi line

Código línea a línea

Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.

bigint.hpp
CódigoSubjectPor qué
#pragma onceQue el .hpp no se incluya dos veces.
#include <iostream>printable with the << operatorstd::ostream para el << que imprime.
#include <string>storing an array or a stringGuardo el número como texto.
#include <sstream>std::ostringstream: pasar el unsigned int del constructor a texto.
#include <cstdlib>std::strtoul: pasar el texto de un bigint a número para desplazar.
class bigint {Create a class called bigintLa clase. Llave en la misma línea: da igual.
private:El texto solo lo toca la propia clase.
std::string s;store an arbitrary precision unsigned integerLos dígitos como texto: 1337 → "1337". Cabe cualquier tamaño. Sin signo = nunca negativo.
public:You will find a main in this directory that must work with your classTodo lo que usa el main.
bigint() : s("0") {}bigint b(21), c, d(1337), e(d);c sin nada vale 0 → "0", no "" (si no, c no imprimiría nada).
bigint(unsigned int n) { std::ostringstream os; os << n; s = os.str(); }const bigint a(42);
((b << 10) + 42)		Desde un número: lo escribo en un ostringstream y saco el texto. Sin explicit: así el 42 suelto se convierte en bigint solo.
bigint(const bigint &oth) : s(oth.s) {}e(d)Copia: copio el texto.
bigint &operator=(const bigint &oth) { s = oth.s; return *this; }Forma canónica. Me cambia → sin const; me devuelvo a mí → bigint &.
~bigint() {}Destructor vacío: el string se libera solo.
bigint operator+(const bigint &oth) const {addition
a + b		Aquí va la suma de verdad. Uno nuevo → bigint; solo miro → const (a es const).
bigint r;El resultado.
r.s = "";Vacío: el constructor lo dejó en "0", y si no lo vacío sale 630 en vez de 63.
int i = s.size() - 1;Último dígito mío (las unidades).
int j = oth.s.size() - 1;Último dígito del otro.
int carry = 0;"Me llevo": empieza en 0.
while (i >= 0 || j >= 0 || carry) {additionSigo mientras me queden dígitos a mí, al otro, o me lleve algo (99 + 1 = 100).
int sum = carry;Empiezo con lo que me llevaba.
if (i >= 0)Si aún me quedan dígitos…
sum += s[i--] - '0';…sumo el mío. - '0' pasa el carácter '7' al número 7. Luego i retrocede.
if (j >= 0)Igual con el otro.
sum += oth.s[j--] - '0';Sumo el suyo.
r.s.insert(r.s.begin(), '0' + sum % 10);El dígito que toca (% 10), de vuelta a carácter, delante del resultado.
carry = sum / 10;Lo que me llevo (0 o 1).
}
return r;Devuelvo el nuevo.
}
bigint &operator+=(const bigint &oth) { return *this = *this + oth; }(c += a)Me sumo con + y me asigno. Me devuelvo a mí.
bigint &operator++() { return *this = *this + 1; }++b++b: me sumo 1 y me devuelvo a mí.
bigint operator++(int) { bigint tmp = *this; *this = *this + 1; return tmp; }b++b++: guardo cómo era, me sumo, devuelvo lo viejo.
bigint operator<<(const bigint &n) const {"digitshift"
(42 << 3 == 42000)
((b << 10) + 42)		Desplazar a la izquierda: uno nuevo, solo miro → const.
bigint r(*this);Una copia de mí.
size_t k = std::strtoul(n.s.c_str(), 0, 10);Cuántos dígitos: el texto de n pasado a número.
if (s != "0")the output should not contain any leading zerosSi valgo 0, desplazar sigue siendo 0: nada de "000".
r.s.append(k, '0');(42 << 3 == 42000)k ceros al final de la copia.
return r;Devuelvo el nuevo.
}
bigint &operator<<=(const bigint &n) { return *this = *this << n; }(d <<= 4)Me desplazo con << y me asigno.
bigint operator>>(const bigint &n) const {(1337 >> 2 == 13)Desplazar a la derecha: uno nuevo.
bigint r(*this);Una copia de mí.
size_t k = std::strtoul(n.s.c_str(), 0, 10);Cuántos dígitos: el texto de n pasado a número.
if (k >= s.size())¿Quito todos o más de los que tengo?
r.s = "0";Quito todos o más → 0.
else
r.s.erase(s.size() - k);(1337 >> 2 == 13)Si no, borro los k últimos.
return r;Devuelvo el nuevo.
}
bigint &operator>>=(const bigint &n) { return *this = *this >> n; }(d >>= (const bigint)2)Me desplazo con >> y me asigno.
bool operator==(const bigint &oth) const { return s == oth.s; }comparison
(d == a)		Mismo texto = mismo número (no hay ceros delante).
bool operator!=(const bigint &oth) const { return !(*this == oth); }(d != a)Lo contrario de ==.
bool operator<(const bigint &oth) const { return s.size() != oth.s.size() ? s.size() < oth.s.size() : s < oth.s; }(d < a)Distinta longitud → el más corto es menor. Misma → compara el texto.
bool operator>(const bigint &oth) const { return oth < *this; }(d > a)a > b es b < a.
bool operator<=(const bigint &oth) const { return !(oth < *this); }(d <= a)a <= b es "no b < a".
bool operator>=(const bigint &oth) const { return !(*this < oth); }(d >= a)a >= b es "no a < b".
friend std::ostream &operator<<(std::ostream &os, const bigint &b) { os << b.s; return os; }printable with the << operator (in base 10)
std::cout << "a = " << a << std::endl;		El << que imprime: friend, escribe el texto en os y devuelve os.
};
bigint.cpp
CódigoSubjectPor qué
#include "bigint.hpp"Expected files : bigint.hpp, bigint.cppEl .cpp es obligatorio, pero todo está en el .hpp: basta con incluirlo.

El main, comentado

El main del subject con una nota en cada línea: qué función de la clase obliga a escribir.

main.cpp
#include "bigint.hpp"	// → #pragma once + <iostream> <string> <sstream> <cstdlib> en el .hpp

int main(void)
{
	const bigint a(42);			// → bigint(unsigned int)    · a es const: todo lo que se le pida a a tiene que ser const
	bigint b(21), c, d(1337), e(d);	// → bigint(unsigned int) · c: bigint() que vale "0" · e(d): bigint(const bigint &)

	// base test
	std::cout << "a = " << a << std::endl;	// → friend operator<<(std::ostream &, const bigint &): el de FUERA, imprime
	std::cout << "b = " << b << std::endl;
	std::cout << "c = " << c << std::endl;	// → por esto bigint() guarda "0" y no "": si no, c no imprimiría nada
	std::cout << "d = " << d << std::endl;
	std::cout << "e = " << e << std::endl;

	std::cout << "a + b = " << a + b << std::endl;	// → bigint operator+(const bigint &) const: la suma del cole · const porque a es const · r.s = "" antes del bucle (si no, sale 630)
	std::cout << "a + c = " << a + c << std::endl;	// → sumar 0 tiene que dar 42 tal cual
	std::cout << "(c += a) = " << (c += a) << std::endl;	// → bigint &operator+=: *this = *this + oth

	std::cout << "b = " << b << std::endl;
	std::cout << "++b = " << ++b << std::endl;	// → bigint &operator++(): devuelve el ya sumado (22)
	std::cout << "b++ = " << b++ << std::endl;	// → bigint operator++(int): devuelve la copia de ANTES (22, y b pasa a 23)

	// b = 23, b << 10 -> 23000000000 + 42 = 23000000042
	std::cout << "(b << 10) + 42 = " << ((b << 10) + 42) << std::endl;	// → operator<<(const bigint &) const: el de DENTRO, añade ceros · 10 y 42 se convierten solos en bigint (constructor sin explicit)
	std::cout << "(d <<= 4) = " << (d <<= 4) << ", d: " << d << std::endl;	// → bigint &operator<<=: *this = *this << n
	std::cout << "(d >>= 2) = " << (d >>= (const bigint)2) << ", d: " << d << std::endl;	// → bigint &operator>>=(const bigint &): el parámetro es const bigint &

	std::cout << "a = " << a << std::endl; // a = 42
	std::cout << "d = " << d << std::endl; // d = 5348

	std::cout << "(d < a) = " << (d < a) << std::endl; // (d < a) = 0		→ operator< const: primero la longitud ("9" < "10"), luego el texto
	std::cout << "(d > a) = " << (d > a) << std::endl; // (d > a) = 1		→ operator>: oth < *this
	std::cout << "(d == d) = " << (d == d) << std::endl; // (d == d) = 1	→ operator==: s == oth.s
	std::cout << "(d != a) = " << (d != a) << std::endl; // (d != a) = 1	→ operator!=: !(*this == oth)
	std::cout << "(d <= a) = " << (d <= a) << std::endl; // (d <= a) = 0	→ operator<=: !(oth < *this)
	std::cout << "(d >= a) = " << (d >= a) << std::endl; // (d >= a) = 1	→ operator>=: !(*this < oth)

	// extra
	bigint x(12345678); bigint y(5);
	std::cout << "(x << y) = " << (x << y) << ", x: " << x << ", y: " << y << std::endl;	// → << con un bigint de verdad a la derecha · x no cambia (const)
	std::cout << "(x >>= y) = " << (x >>= y) << ", x: " << x << ", y: " << y << std::endl;	// → operator>>= (usa >>): quita dígitos del final (12345678 → 123)
	std::cout << "(x >= y) = " << (x >= y) << ", x: " << x << ", y: " << y << std::endl;

	std::cout << "x= " << (x <<= 5) << ", y= " << (y <<= 12) << std::endl;	// → y pasa a 5000000000000: más grande que un unsigned int → por eso se guarda como string
	std::cout << "(x >= y) = " << (x >= y) << ", x: " << x << ", y: " << y << std::endl;	// → 8 dígitos contra 13: gana el más largo

	return (0);
}	// → aquí se destruyen todos: ~bigint() vacío, el string se libera solo