Преобразование двоичного представления в троичное

Question

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

Решение, которое я уже реализовал, - сначала преобразовать число в десятичное, а затем преобразовать его в требуемую систему счисления.Это работает, но есть два шага.Интересно, можно ли сделать это за один шаг, не применяя сначала троичную арифметику?Ребята, есть какая-то хитрость?

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

data BDigit = B0 | B1
type BNumber = [BDigit]

data TDigit = T0 | T1 | T2
type TNumber = [TDigit]

И есть два очевидных способа преобразовать один в другой: первый - преобразовать его в целое числово-первых и получить результат (неинтересный способ), во-вторых, реализовать собственное умножение и сложение в base-3 и вычислить результат умножения значений цифр до соответствующей степени двух (прямое и тяжелое).

Итак, я 'Мне интересно, есть ли другой метод, чем эти два.

Answer 1

Если вы делаете это с компьютером, то все уже в двоичном формате, поэтому просто несколько раз разделить на 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

Answer 2

Я думаю, что все упускают что-то важное.Во-первых, заранее вычислите таблицу, для каждого двоичного бита нам нужно представление в троичной форме.В 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

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

Answer 3

Вы можете использовать некоторые умные сокращения для преобразования.Следующий код является «неправильным» направлением, это преобразование из троичного в двоичное, основанное на том факте, что 3 ^ 2 = 2 ^ 3 + 1 с использованием только двоичного сложения.По сути, я конвертирую две троичные цифры в три двоичные цифры.От двоичного к троичному будет немного сложнее, так как потребуется троичное сложение (и, возможно, вычитание) (работая над этим).Я предполагаю, что наименее значимая цифра в начале списка (это единственный способ, который имеет смысл), поэтому вы должны читать цифры «назад».

addB :: BNumber → BNumber → BNumber
addB a [] = a
addB [] b = b
addB (B0:as) (B0:bs) = B0 : (addB as bs) 
addB (B0:as) (B1:bs) = B1 : (addB as bs)
addB (B1:as) (B0:bs) = B1 : (addB as bs)
addB (B1:as) (B1:bs) = B0 : (addB (addB as bs) [B1])

t2b :: TNumber → BNumber
t2b [] = []
t2b [T0] = [B0]
t2b [T1] = [B1]
t2b [T2] = [B0,B1]
t2b (T2:T2:ts) = let bs = t2b ts in addB bs (B0:B0:B0:(addB bs [B1]))
t2b (t0:t1:ts) = 
   let bs = t2b ts
       (b0,b1,b2) = conv t0 t1
   in addB bs (b0:b1:b2:bs) 
   where conv T0 T0 = (B0,B0,B0)
         conv T1 T0 = (B1,B0,B0)
         conv T2 T0 = (B0,B1,B0)
         conv T0 T1 = (B1,B1,B0)
         conv T1 T1 = (B0,B0,B1)
         conv T2 T1 = (B1,B0,B1)
         conv T0 T2 = (B0,B1,B1)
         conv T1 T2 = (B1,B1,B1)

[Редактировать] Вотдвоично-троичное направление, как и ожидалось, немного длиннее:

addT :: TNumber → TNumber → TNumber
addT a [] = a
addT [] b = b
addT (T0:as) (T0:bs) = T0 : (addT as bs) 
addT (T1:as) (T0:bs) = T1 : (addT as bs)
addT (T2:as) (T0:bs) = T2 : (addT as bs)
addT (T0:as) (T1:bs) = T1 : (addT as bs) 
addT (T1:as) (T1:bs) = T2 : (addT as bs)
addT (T2:as) (T1:bs) = T0 : (addT (addT as bs) [T1])
addT (T0:as) (T2:bs) = T2 : (addT as bs)
addT (T1:as) (T2:bs) = T0 : (addT (addT as bs) [T1])
addT (T2:as) (T2:bs) = T1 : (addT (addT as bs) [T1])

subT :: TNumber → TNumber → TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (T0:as) (T0:bs) = T0 : (subT as bs) 
subT (T1:as) (T0:bs) = T1 : (subT as bs)
subT (T2:as) (T0:bs) = T2 : (subT as bs)
subT (T0:as) (T1:bs) = T2 : (subT as (addT bs [T1])) 
subT (T1:as) (T1:bs) = T0 : (subT as bs)
subT (T2:as) (T1:bs) = T1 : (subT as bs)
subT (T0:as) (T2:bs) = T1 : (subT as (addT bs [T1]))
subT (T1:as) (T2:bs) = T2 : (subT as (addT bs [T1]))
subT (T2:as) (T2:bs) = T0 : (subT as bs)

b2t :: BNumber → TNumber
b2t [] = []
b2t [B0] = [T0]
b2t [B1] = [T1]
b2t [B0,B1] = [T2]
b2t [B1,B1] = [T0,T1]
b2t (b0:b1:b2:bs) = 
   let ts = b2t bs
       (t0,t1) = conv b0 b1 b2
   in subT (t0:t1:ts) ts
   where conv B0 B0 B0 = (T0,T0)
         conv B1 B0 B0 = (T1,T0)
         conv B0 B1 B0 = (T2,T0)
         conv B1 B1 B0 = (T0,T1)
         conv B0 B0 B1 = (T1,T1)
         conv B1 B0 B1 = (T2,T1)
         conv B0 B1 B1 = (T0,T2)
         conv B1 B1 B1 = (T1,T2)

[Edit2] Немного улучшенная версия subT, которая не требует addT

subT :: TNumber →  TNumber →  TNumber
subT a [] = a
subT [] b = error "negative numbers supported"
subT (a:as) (b:bs) 
  | b ≡ T0 = a : (subT as bs)
  | a ≡ b =  T0 : (subT as bs)
  | a ≡ T2 ∧ b ≡ T1 =  T1 : (subT as bs)
  | otherwise = let td = if a ≡ T0 ∧ b ≡ T2 then T1 else T2 
                in td : (subT as $ addTDigit bs T1)  
    where addTDigit [] d = [d]
          addTDigit ts T0 =  ts
          addTDigit (T0:ts) d = d:ts 
          addTDigit (T1:ts) T1 = T2:ts
          addTDigit (t:ts) d = let td = if t ≡ T2 ∧ d ≡ T2 then T1 else T0
                               in td : (addTDigit ts T1)

Answer 4

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

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

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

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

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

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

.. тоже

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

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

Answer 8

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

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

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

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

---

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

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