Manipulation de bits pour les grandes classes entières?

Question

J'ai un problème avec un algorithme pour une grande classe entière en C++. Mon idée initiale était d'utiliser des tableaux/listes, mais c'est très inefficace. J'ai alors découvert des choses comme la classe suivante: http://www.codeproject.com/KB/cpp/CppIntegerClass.aspx

Cependant, je trouve cette approche vraiment déroutante. Je ne sais pas comment travailler avec des manipulations de bits, et j'ai à peine compris le code. Quelqu'un peut m'expliquer comment utiliser la manipulation des bits, comment cela fonctionne, etc. Finalement, je voudrais créer ma propre classe de nombres entiers, mais je suis à peine un programmeur novice et j'ai juste appris à utiliser les classes.

Au fond ma question est: Comment puis-je utiliser la manipulation de bits pour créer une grande classe entière? Comment ça marche??

Merci!

Answer 1

Commencez par lire sur binary numbers en général. Cette page montre comment les opérations arithmétiques communes (addition, soustraction, etc.) fonctionnent sur des nombres binaires, c'est-à-dire comment les nombres sont manipulés petit à petit pour obtenir le résultat souhaité.

Mapper cela dans un langage de programmation tel que C++ devrait être assez simple une fois que vous savez pourquoi il y a des opérations de manipulation de bits utilisées. Dans mon expérience, la chose la plus évidente orientée bits nécessaire lors de l'implémentation de ce type de comportement est le bit testant, pour vérifier le dépassement. Supposons que vous représentez votre grand nombre binaire sous la forme d'un tableau de uint16_t, c'est-à-dire des blocs de 16 bits. Lors de l'implémentation de l'addition, vous commencerez à la fin la moins significative des deux nombres, et vous les ajouterez. Si la somme est supérieure à 65 535, vous devez "reporter" l'un sur l'autre uint16_t, tout comme lorsque vous ajoutez des nombres décimaux un chiffre à la fois.

Cela peut être mis en œuvre avec un test comme ceci:

const uint16_t *number1; 
const uint16_t *number2; 

/* assume code goes here to set up the number1 and number2 pointers. */ 

/* Compute sum of 16 bits. */ 
uint16_t carry = 0; 
uint32_t sum = number1[0] + number2[0]; 

/* One way of testing for overflow: */ 
if (sum & (1 << 16)) 
carry = 1; 

Ici, les expressions 1 << 16 crée un masque en déplaçant un 1 seize étapes vers la gauche. Le bit & et l'opérateur teste la somme par rapport au masque; le résultat sera non nul (c'est-à-dire vrai, en C++) si le bit 16 est défini en sum.