Преобразовать массив десятичных цифр в массив двоичных цифр - PullRequest
Новая
       9

Преобразовать массив десятичных цифр в массив двоичных цифр

2 голосов
/ 01 ноября 2009

Это, наверное, довольно экзотический вопрос.

Моя проблема заключается в следующем:

Графический калькулятор TI 83+ позволяет программировать его, используя сборку и кабель связи с компьютером, или его встроенный язык программирования TI-BASIC.

Согласно тому, что я нашел, он поддерживает только 16-битные целые числа и некоторые эмулируемые числа с плавающей запятой.

Однако я хочу работать с немного большими числами (около 64 бит), поэтому для этого я использую массив с одной цифрой: 

{1, 2, 3, 4, 5}

будет десятичным 12345.

В двоичном виде это 110000 00111001 или в виде двоичного массива: 

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

это будет то, как калькулятор отображает это.

Как мне преобразовать этот массив десятичных цифр (который слишком велик для калькулятора, чтобы отобразить его как собственный тип) в массив десятичных цифр?

Эффективность не проблема. Это НЕ домашнее задание.

Это освободило бы меня для реализации сложения для таких массивов и тому подобного.

спасибо!

Ответы [ 3 ]

1 голос
/ 01 ноября 2009

Думал об этом, и я думаю, что сделал бы это со следующим 'алгоритмом'

  • проверить последнюю цифру (5 в примере)

  • если это нечетно, сохранить (в обратном порядке) 1 в двоичном массиве

  • теперь разделите число на 2 следующим способом:

  • начинаются с первой цифры и очищают переменную 'carry'.
  • разделите его на 2 и добавьте переменную 'carry'. Если остаток равен 1 (проверьте это перед делением с помощью & и 1), затем положите 5 в керри
  • повторяется до тех пор, пока не будут выполнены все цифры

повторите оба шага снова, пока все число не уменьшится до 0.

число в вашем двоичном массиве является двоичным представлением

ваш пример: 1,2,3,4,5

  • 5 нечетно, поэтому мы храним 1 в двоичном массиве: 1
  • делим массив на 2 по алгоритму:
  • 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

и повторите:

0,6,1,7,2 последняя цифра четная, поэтому мы храним 0: 0,1 (обратите внимание, мы заполняем двоичную строку справа налево)

и т.д.

вы получите двоичный код

EDIT: Просто чтобы уточнить выше: все, что я делаю, это старый алгоритм: 

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

за исключением того, что в вашем примере у нас есть не int, а массив, который представляет (10 base) int; ^)

0 голосов
/ 01 ноября 2009

По пути можно будет преобразовать каждую цифру в десятичном представлении в ее двоичное представление, а затем добавить двоичные представления всех цифр: 

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

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

Доказательство концепции в C #:

Методы преобразования в массив двоичных цифр, добавления массивов и умножения массива на десять: 

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;
}

Преобразование массива: 

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()
);

Выход: 

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

Edit:
Добавлены методы умножения массива на десятки. Вместо того, чтобы умножить цифру перед преобразованием ее в двоичный массив, она должна быть сделана с массивом.

0 голосов
/ 01 ноября 2009

Основная проблема здесь заключается в том, что вы переходите между базами, которые не кратны друг другу, и, следовательно, нет прямого изолированного отображения между входными и выходными цифрами. Вероятно, вам придется начинать с наименее значащей цифры, выводить как можно меньше наименее значимых цифр, прежде чем обращаться к следующей цифре, и так далее. Таким образом, вам нужно, чтобы в любой момент времени было проверено не более 2 ваших входных цифр.

Может оказаться полезным с точки зрения порядка обработки хранить ваши числа в обратном порядке (чтобы младшие значащие цифры были первыми в массиве).

...