Convertir un tableau de chiffres décimaux en un tableau de chiffres binaires

Question

Il s'agit probablement d'une question assez exotique.

Mon problème est le suivant :

La calculatrice graphique TI 83+ vous permet de programmer en utilisant soit Assembly et un câble de liaison à un ordinateur, soit son langage de programmation TI-BASIC intégré.

D'après ce que j'ai trouvé, il ne prend en charge que les entiers de 16 bits et quelques flottants émulés.

Cependant, je veux travailler avec des nombres un peu plus grands (autour de 64 bits), donc pour cela j'utilise un tableau avec les chiffres simples :

{1, 2, 3, 4, 5}

serait la valeur décimale 12345.

En binaire, c'est 110000 00111001, ou en tant que tableau de chiffres binaires :

{1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1}

ce qui correspond à la façon dont la calculatrice l'affiche.

Comment convertir ce tableau de chiffres décimaux (qui est trop grand pour que la calculatrice l'affiche comme un type natif) en un tableau de chiffres décimaux ?

L'efficacité n'est pas un problème. Il ne s'agit PAS d'un travail à domicile.

Cela me laisserait libre d'implémenter l'addition pour ces tableaux et autres.

merci !

Answer 1

J'y ai réfléchi et je pense que je le ferais avec l'"algorithme" suivant

• vérifier le dernier chiffre (5 dans l'exemple)

• s'il est impair, stocker (dans l'ordre inverse) un 1 dans le tableau binaire

• divisez maintenant le nombre par 2 en appliquant la méthode suivante :

• commence par le premier chiffre et efface la variable "carry".

• diviser par 2 et ajouter la variable "carry". Si le reste est 1 (vérifiez-le avant de diviser avec un et&1), mettez 5 dans la variable "carry".

• Répéter jusqu'à ce que tous les chiffres aient été effectués

répéter les deux étapes jusqu'à ce que le nombre entier soit réduit à des 0.

le nombre dans votre tableau binaire est la représentation binaire

votre exemple : 1,2,3,4,5

• le 5 est impair, nous stockons donc 1 dans le tableau binaire : 1
• nous divisons le tableau par 2 à l'aide de l'algorithme :
• 0,2,3,4,5 => 0,1+5,3,4,5 => 0,6,1,4,5 => 0,6,1,2+5,5 => 0,6,1,7,2

et répéter :

0,6,1,7,2 le dernier chiffre est pair donc nous stockons un 0 : 0,1 (remarquez que nous remplissons la chaîne binaire de droite à gauche)

etc.

on se retrouve avec un binaire

EDIT : Juste pour clarifier ce qui précède : Tout ce que je fais, c'est le vieil algorithme :

 int value=12345;
 while(value>0)
 {
      binaryArray.push(value&1);
      value>>=1;     //divide by 2
 }

sauf que dans votre exemple nous n'avons pas un int mais un array qui représente un int (base 10) ;^)

Answer 2

Une solution consisterait à convertir chaque chiffre de la représentation décimale en sa représentation binaire, puis à additionner les représentations binaires de tous les chiffres :

5 = 101
40 = 101000
300 = 100101100
2000 = 11111010000
10000 = 10011100010000

             101
          101000
       100101100
     11111010000
+ 10011100010000
----------------
  11000000111001

Preuve de concept en C# :

Méthodes de conversion en un tableau de chiffres binaires, d'addition de tableaux et de multiplication d'un tableau par dix :

private static byte[] GetBinary(int value) {
  int bit = 1, len = 1;
  while (bit * 2 < value) {
    bit <<= 1;
    len++;
  }
  byte[] result = new byte[len];
  for (int i = 0; value > 0;i++ ) {
    if (value >= bit) {
      value -= bit;
      result[i] = 1;
    }
    bit >>= 1;
  }
  return result;
}

private static byte[] Add(byte[] a, byte[] b) {
  byte[] result = new byte[Math.Max(a.Length, b.Length) + 1];
  int carry = 0;
  for (int i = 1; i <= result.Length; i++) {
    if (i <= a.Length) carry += a[a.Length - i];
    if (i <= b.Length) carry += b[b.Length - i];
    result[result.Length - i] = (byte)(carry & 1);
    carry >>= 1;
  }
  if (result[0] == 0) {
    byte[] shorter = new byte[result.Length - 1];
    Array.Copy(result, 1, shorter, 0, shorter.Length);
    result = shorter;
  }
  return result;
}

private static byte[] Mul2(byte[] a, int exp) {
  byte[] result = new byte[a.Length + exp];
  Array.Copy(a, result, a.Length);
  return result;
}

private static byte[] Mul10(byte[] a, int exp) {
  for (int i = 0; i < exp; i++) {
    a = Add(Mul2(a, 3), Mul2(a, 1));
  }
  return a;
}

Conversion d'un tableau :

byte[] digits = { 1, 2, 3, 4, 5 };

byte[][] bin = new byte[digits.Length][];
int exp = 0;
for (int i = digits.Length - 1; i >= 0; i--) {
  bin[i] = Mul10(GetBinary(digits[i]), exp);
  exp++;
}
byte[] result = null;
foreach (byte[] digit in bin) {
  result = result == null ? digit: Add(result, digit);
}

// output array
Console.WriteLine(
  result.Aggregate(
    new StringBuilder(),
    (s, n) => s.Append(s.Length == 0 ? "" : ",").Append(n)
  ).ToString()
);

Sortie :

1,1,0,0,0,0,0,0,1,1,1,0,0,1

Editer :
Ajout de méthodes pour multiplier un tableau par dizaines. Au lieu de multiplier le chiffre avant de le convertir en tableau binaire, il faut le faire sur le tableau.

Answer 3

Le principal problème est que vous passez d'une base à une autre qui n'est pas un multiple d'une autre, et qu'il n'y a donc pas de correspondance directe et isolée entre les chiffres d'entrée et les chiffres de sortie. Vous devrez probablement commencer par le chiffre le moins significatif, sortir autant de chiffres les moins significatifs de la sortie que possible avant de devoir consulter le chiffre suivant, et ainsi de suite. De cette manière, vous n'aurez besoin d'examiner que deux de vos chiffres d'entrée au maximum à un moment donné.

Il peut être avantageux, en termes d'ordre de traitement, de stocker vos nombres sous forme inversée (de sorte que les chiffres les moins significatifs viennent en premier dans le tableau).