Двоичный файл к троичному преобразованию представления

Если вы делаете это на компьютере, все уже представлено в двоичном формате, поэтому просто многократное деление на 3 и получение остатка почти так же просто.

Если вы делаете это вручную, длинное деление в двоичном формате работает так же, как длинное деление в десятичном. просто разделите на три и возьмите остаток. если мы начнем с 16

   ___101
11 |10000
     11
      100
       11
        1   

100000 / 11 = 101 + 1/11 so the least significnnt digit is 1

101/ 11 = 1 + 10/11  the next digit is 2

1  and the msd is 1

, то в троичной системе 121

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

dec2base(2.^(0:10),3)
ans =
0000001
0000002
0000011
0000022
0000121
0001012
0002101
0011202
0100111
0200222
1101221

Теперь рассмотрим двоичное число 011000101 (которое оказывается десятичным числом 197, как мы узнаем позже). Извлеките троичное представление для каждого двоичного бита из таблицы. Выпишу соответствующие строки.

0000001 
0000011
0002101
0011202

Теперь просто суммируйте. Мы получаем это представление в непереносимой троичной системе.

0013315

Да, это не троичные числа, но они почти в корректном представлении с основанием 3. Теперь все, что вам нужно сделать, это сделать перенос. Начните с цифры единиц.

5 больше 2, поэтому отнимите количество, кратное 3, и увеличьте вторую цифру результата соответствующим образом.

0013322

Теперь вторая цифра равна 2, законной троичной цифре, поэтому переходите к третьей цифре. Сделайте и этот перенос,

0014022

Наконец, получив теперь полностью верное троичное число ...

0021022

Были ли мои вычисления правильными? Я позволю MATLAB вынести окончательное решение за нас:

base2dec('011000101',2)
ans =
   197

base2dec('0021022',3)
ans =
   197

Я указал, насколько тривиальной была эта операция, что я мог выполнить преобразование полностью вручную, переходя по существу напрямую от двоичного кода к троичному, по крайней мере, когда я получил это начальная таблица записана и сохранена?

Если это домашнее задание, псевдокод для записи x в базе b в обратном порядке:

while (x != 0) {
    q <-- x/b
    r <-- x - q*b
    print r
    x <-- q
}

Я уверен, что вы можете понять, как напишите результат вперед, а не назад. Обратите внимание, что / должно быть целочисленным делением в стиле C (результат - целое число, усеченное до нуля).

Обратите внимание, что это не зависит вообще от базы, на которой выполняется арифметика. Арифметика определяется на целых числах, а не на представлении целых чисел в определенной базе.

Изменить: Основываясь на вашем обновленном вопросе, я бы преобразовал цифровое представление в целое число (с помощью или и сдвигов) и использовал алгоритм, описанный выше, с целочисленной арифметикой.

Конечно, вы могли бы сделать это так, как вы описываете, но это похоже на ужасно много работы.

Боюсь, я не знаю достаточно языка Haskell, чтобы выразить это в коде, но мне интересно, может ли использование правила Хорнера для оценки многочленов дать метод.

Например, ax^2 + bx + c может быть оценено как c+x*(b+x*a).

Чтобы преобразовать, скажем, троичное число a*9+b*3+c в двоичное, нужно начать с двоичного представления a, затем умножить его на 3 (т.е. сдвинуть и сложить), затем сложить двоичное представление b, умножить результат на 3 и добавить c.

Мне кажется, это можно сделать с помощью карты (чтобы получить двоичное представление троичных цифр) и сложения (a,b -> a+3*b)

Нет, вы не можете преобразовать число base2 в число base3, не загружая его в целое число. Причина в том, что 2 и 3 являются простыми - у них нет общих множителей.

Если бы вы работали с основаниями 2 и 4, или даже с основаниями 6 и 9, то набор целых чисел до наименьшего общего кратного этих двух оснований был бы представлен двумя изоморфными наборами. Например, 13 (основание4) = 0111 (основание2), поэтому преобразование 1313 (основание4) = 01110111 (основание2) - это операция поиска и замены.

По крайней мере, решение, которое вы имеете, работает и является относительно простым. Если вам нужно повысить производительность, преобразуйте все представление base2 в целое число перед началом преобразования base3; это означает меньше операций с модулями. Альтернативой может быть обработка каждого символа в числе base2 по одному, в этом случае вы будете делить на все степени 3 для каждой цифры в представлении base2.

Я думаю, что могут быть разные "взгляды" на проблему, хотя я не уверен, что какие-то из них быстрее или лучше. Например, цифра n по основанию 3 младшего разряда равна n по модулю 3. Допустим, у вас уже есть двоичное представление числа n. Затем рассмотрим, как степени двойки работают по модулю 3. 2 ^ 0 = 1 по модулю 3, 2 ^ 1 = 2 по модулю 3, 2 ^ 2 = 1 по модулю 3, 2 ^ 3 = 2 по модулю 3, ... Другими словами , степени чередуются между 1 по модулю 3 и 2 по модулю 3. Теперь у вас есть простой способ получить 3-ю цифру младшего разряда, сканируя двоичное представление n и обычно добавляя только 1 или 2 в каждой битовой позиции. где встречается 1.

Я не думаю, что есть сверхэффективный способ.

«Решение, которое я уже реализовал преобразовать число в десятичное first. "

Я предполагаю, что вы сначала конвертируете в какой-то встроенный целочисленный тип. Я не думаю, что встроенное целое число имеет какое-либо отношение к основанию 10. (Хотя, когда вы его распечатываете, он будет будет преобразованием по основанию 10.

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

Но, скажем, вы хотите преобразовать 3486784400 (основание 10) по основанию 3. Вам нужно будет проверить каждую цифру перед выводом, потому что

3486784401 (base 10) = 100000000000000000000 (base 3)
3486784400 (base 10) =  22222222222222222222 (base 3)

.. также

"вычисляют результат умножения цифры значения в соответствующую степень двойки "

явное вычисление степени не требуется, см. преобразование из базы 60 в основание 10