Du 36 bits dans un sytème 32 bits

**SmLBernard** · 08/10/2009, 16h33

Bonjour,

actuellement en étude, nous avons à nous pencher sur un cas qui a du en faire réfléchir plus d'un avant nous.

Faire en sorte de convertir un entier 36bits en décimal, mais sur un système ou int est de 16 bits et long 32bits.

Notre souci est de pouvoir stocker une valeur au delà de 4.294.967.294 (un long donc) pour ensuite le convertir en binaire.

un petit coup de pouce serait vraiment pas du luxe car nous bloquons.

Cordialement.

**ram-0000** · 08/10/2009, 16h44

l'utilisation du long long int (64 bits même sur un système 32 bits) est interdite ?

**SmLBernard** · 08/10/2009, 16h59

Bonne question car il n'a pas été précisé dans le sujet. Mais d'après l'algorithme (puis C) demandé, nous devons nous débrouiller avec des int et long. Ce qui pour l'instant pose un souci rien qu'au niveau de la saisie de l'utilisateur si le chiffre est > à 32 bits.

**droggo** · 08/10/2009, 17h39

Voa,

Si la limite max est précisée, et entre dans les possibilités d'un long long, il vous suffit de développer l'équivalent (avec peut-être les princilales fonctions pour l'utiliser ?).

Sinon, il faut faire une bibliothèque de calcul multi-précision sans limite, genre GMP (voir google

).

**Mac LAK** · 08/10/2009, 17h46

Si c'est un exercice, le but est "simplement" de te faire faire les opérations de changement de base à la main, je pense... En l'occurrence, découper ton nombre en nibbles (4 bits), stockés séparéments, et constituant au final un nombre de 9 chiffres hexadécimaux.

Bref, faire de l'arithmétique en multiprécision de façon "manuelle". Normalement, l'étape suivante, ce sera d'implémenter les opérations arithmétiques usuelles (addition, soustraction, multiplication et division, cette dernière étant la plus marrante bien sûr).

**SmLBernard** · 10/10/2009, 16h47

En effet Mac Lak, tu as bien vu mon problème. Il existe donc un moyen pour stocké une valeur supérieure à 4 octets.

Ce que je cerne pas trop c'est :

Lorsque l'utilisateur saisie un nombre supérieure à 4 octets, comment la stocker ensuite si je suis limité par mon long.

Si j'ai bien compris ton idée il me faut la fractionner, mais par quelle méthode ?

**Mac LAK** · 10/10/2009, 17h42

Oh, très bêtement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
//! Définition d'un entier 36 bits.
typedef struct {
    //! Vaut "1" si l'entier a débordé (overflow), "0" sinon.
    char overflow ;
    //! Vaut "0" si l'entier est positif, "1" s'il est négatif.
    char sign ;
    //! Chaque "char" contient 4 bits utiles (poids faible), plus assez d'espace pour les retenues.
    char digits[9] ;
} int36bits ;

Il te faudra ensuite une fonction de normalisation, qui va prendre une structure int36bits et va propager les retenues éventuelles, et garantir la condition suivante :
quel que soit i, 0<=i<9, 0<=digits[i]<16
Ainsi, chaque chiffre unitaire est bien un "vrai" chiffre hexa entre 0 et 15 inclus.

De cette façon, tu effectues les opérations "unitairement" de façon vectorielle (chiffre à chiffre), puis la normalisation va effectuer la propagation des retenues. Si tu débordes trop, tu positionnes overflow et tu sais alors que le chiffre affiché est faux. C'est un cas plus que probable : si tu prends 0xFFFFFFFFF (le plus grand entier positif sur 36 bits en NON-signé), et que tu l'augmentes de 1, tu obtiens 0x1000000000, qui ne peut pas tenir en moins de 37 bits => overflow. Avec les multiplications, c'est encore pire, bien entendu : la multiplication d'un nombre de N bits par un nombre de M bits requiert un entier (N + M) (EDIT : et non pas (N x M)...) bits pour être stocké, de façon générale.

**Obsidian** · 10/10/2009, 23h14

Attention, Mac Lak, SmLBernard veut convertir un entier naturel binaire en décimal ! Pas en hexa. Inventer une structure composite dans laquelle on n'utilise que la moitié des bits, non seulement ce n'est pas très efficace, mais c'est aussi inutile d'un point de vue arithmétique.

Il n'y a pas trente-six manières de convertir un nombre, quel qu'il soit, dans une base donnée : il faut diviser successivement ce nombre par ladite base, aligner le reste à chaque fois, et relire le résultat en sens inverse. Dans le cas qui nous intéresse, on va diviser n fois par 10, soit 0x0A ou 1010b (ceci pour montrer qu'un nombre rond dans une base ne l'est pas forcément dans une autre).

Exemple : 342 ÷ 10 = 34, reste 2 ; 34 ÷ 10 = 3, reste 4 ; 3 ÷ 10 = 0 reste 3. Soit 3⋅4⋅2, de droite à gauche.

Ensuite, pour diviser (par 10 ou n'importe quelle autre valeur) un nombre de longueur arbitraire, on fait exactement comme on le fait sur papier à l'école : on procède par tranches, on réduit la première, on « descend » la suivante, et on continue jusqu'à la dernière.

En l'occurence, étant donné que l'on dispose de registres de 32 bits, le mieux est d'utiliser des tranches de 16 bits. Dès que l'on arrive en dessous de 10, on la multiple par 65536 (2^16) pour la décaler vers la gauche et on ajoute (ou superpose avec un OU), la tranche suivante, et on itère.

À noter que c'est intéressant si l'on dispose déjà de primitives de division sur des registres de taille donnée. Sinon, le plus efficace reste de travailler directement au niveau du bit : en effet, en base 10, on peut faire jusqu'à 9 soustractions successives par tranches, en base 65536 jusqu'à 65535 (!), et en base 2 ... une seule ! Ce qui était une itération devient alors une simple décision. Lors de la comparaison des grandeurs des deux champs (diviseur et dividende), le bit qui les compare donne directement le résultat de l'opération en cours.

**Mac LAK** · 11/10/2009, 12h38

Envoyé par Obsidian

Attention, Mac Lak, SmLBernard veut convertir un entier naturel binaire en décimal ! Pas en hexa. Inventer une structure composite dans laquelle on n'utilise que la moitié des bits, non seulement ce n'est pas très efficace, mais c'est aussi inutile d'un point de vue arithmétique.

C'est pour l'exemple : si tu utilises du BCD, tu as encore plus de pertes. Le seul stockage efficace sur un ordinateur consiste à utiliser des bases qui sont des puissances de deux, on le sait tous.

En l'occurrence, le stockage importe assez peu ici : c'est un "cas d'école", si l'on voulait réellement être efficace au mieux, on utiliserait une base 2^32 (voire 2^16) pour cette opération !

L'avantage d'utiliser une base 16 et des "registres" doublés, c'est que les opérations sont simples mais multiples (9 "registres" et non pas deux seulement en base 2^32), donc cela montre bien qu'il a compris le principe. De plus, le demi-registre supplémentaire est une aide précieuse pour la propagation des retenues.