Un défi amusant. :)
Je suppose que vous voulez des entiers de taille arbitraire. Je vous propose la démarche suivante:
Considérer la nature binaire du type "int". Penser à l'aide de simples opérations binaires pour imiter ce que les circuits de votre CPU n'lorsqu'ils ajoutent des choses. Dans le cas où vous êtes intéressé plus en profondeur, il est conseillé de lire cet article de wikipédia sur la demi-additionneurs et plein additionneurs. Vous allez faire quelque chose de semblable à cela, mais vous pouvez descendre aussi bas niveau que celle - mais paresseuse, je pensais que je voudrais simplement renoncer à et de trouver une solution plus simple.
Mais avant d'aller dans n'importe quel algorithmique des détails sur l'ajout, soustraction, la multiplication, nous allons trouver des données de la structure. Une manière simple, est bien sûr, pour stocker des choses dans un std::vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
Vous pourriez envisager si vous souhaitez faire le vecteur d'une taille fixe et si de préallouer. La raison en est que pour diverses opérations, vous aurez à passer par chaque élément du vecteur - O(n). Vous voulez savoir comment désinvolte complexe d'une opération est un fixe n est juste que.
Mais maintenant, pour certains algorithmes d'exploitation sur les nombres. Vous pourriez le faire sur une logique de niveau, mais nous allons utiliser cette magie, la puissance du PROCESSEUR pour calculer les résultats. Mais ce que nous allons prendre la relève de la logique-illustration de la Moitié - et FullAdders est la façon dont il traite avec porte. Par exemple, considérez comment vous pouvez mettre en œuvre l' opérateur+= . Pour chaque numéro de type BigInt<>::value_, vous devez ajouter à ceux-ci et voir si le résultat produit une certaine forme de portage. Nous n'allons pas faire de bit-wise, mais dépendent de la nature de notre BaseType (que ce soit long ou int ou de courte ou de quoi que ce soit): il déborde.
Sûrement, si vous ajoutez les deux chiffres, le résultat doit être supérieure à la plus un de ces numéros, à droite? Si elle ne l'est pas, alors le résultat débordé.
template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
L'autre opération arithmétique aller analogue. Heck, vous pouvez même utiliser la stl-foncteurs std::plus et std::moins, std::temps et std::divise, ..., mais l'esprit de la transporter. :) Vous pouvez aussi mettre en œuvre la multiplication et la division à l'aide de votre plus et moins opérateurs, mais c'est très lent, parce que ce serait recalculer les résultats que vous avez déjà calculé en avant les appels à plus et moins à chaque itération. Il y a beaucoup de bons algorithmes pour cette tâche simple, utiliser wikipédia ou sur le web.
Et bien sûr, vous devez mettre en œuvre la norme des opérateurs tels que operator<< (passez chaque valeur de value_ à gauche de n bits, en commençant à l' value_.size()-1... oh et n'oubliez pas le porter :), operator< - vous pouvez même optimiser un peu ici, la vérification de la rugueuse nombre de chiffres avec size() première. Et ainsi de suite. Faites ensuite votre classe utile, par befriendig std::ostream operator<<.
Espérons que cette approche est utile!
