二进制到三进制表示转换

Question

是否有人知道(或可能指向某些来源阅读)将二进制数字系统中表示的数字转换为三元数(我的特定情况)的方法或算法,或者用于此类转换的通用算法？

我已经实现的解决方案是先将数字转换为十进制,然后将其转换为所需的数字系统.这有效,但有两个步骤.我想知道如果不首先实施三元算法,是否可以一步完成？伙计们,有什么诀窍吗？

UPD:我似乎无法清楚地描述我正在寻找哪种转换方式.我不要求对一些办法基2转换为基3,我知道如何做到这一点.您可能会认为我有三元数和二进制数的代数数据结构,在Haskell中它看起来像这样:

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

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

并且有两种明显的方法可以将一个转换为另一个:首先是将其转换为Integer并获得结果(不是有趣的方式),其次是在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

您可以使用一些巧妙的缩写进行转换。下面的代码是“错误”的方向，它是基于仅使用二进制加法的3^2 = 2^3 + 1这一事实从三进制到二进制的转换。基本上我将两个三进制数字转换为三个二进制数字。从二进制到三进制会稍微复杂一些，因为需要三进制加法（可能还需要减法）（正在处理）。我假设列表开头的最低有效数字（这是唯一有意义的方法），因此您必须“向后”读取数字。

\n\n

addB :: BNumber \xe2\x86\x92 BNumber \xe2\x86\x92 BNumber\naddB a [] = a\naddB [] b = b\naddB (B0:as) (B0:bs) = B0 : (addB as bs) \naddB (B0:as) (B1:bs) = B1 : (addB as bs)\naddB (B1:as) (B0:bs) = B1 : (addB as bs)\naddB (B1:as) (B1:bs) = B0 : (addB (addB as bs) [B1])\n\nt2b :: TNumber \xe2\x86\x92 BNumber\nt2b [] = []\nt2b [T0] = [B0]\nt2b [T1] = [B1]\nt2b [T2] = [B0,B1]\nt2b (T2:T2:ts) = let bs = t2b ts in addB bs (B0:B0:B0:(addB bs [B1]))\nt2b (t0:t1:ts) = \n   let bs = t2b ts\n       (b0,b1,b2) = conv t0 t1\n   in addB bs (b0:b1:b2:bs) \n   where conv T0 T0 = (B0,B0,B0)\n         conv T1 T0 = (B1,B0,B0)\n         conv T2 T0 = (B0,B1,B0)\n         conv T0 T1 = (B1,B1,B0)\n         conv T1 T1 = (B0,B0,B1)\n         conv T2 T1 = (B1,B0,B1)\n         conv T0 T2 = (B0,B1,B1)\n         conv T1 T2 = (B1,B1,B1)\n

\n\n

[编辑] 这是二进制到三进制的方向，正如预期的那样有点长：

\n\n

addT :: TNumber \xe2\x86\x92 TNumber \xe2\x86\x92 TNumber\naddT a [] = a\naddT [] b = b\naddT (T0:as) (T0:bs) = T0 : (addT as bs) \naddT (T1:as) (T0:bs) = T1 : (addT as bs)\naddT (T2:as) (T0:bs) = T2 : (addT as bs)\naddT (T0:as) (T1:bs) = T1 : (addT as bs) \naddT (T1:as) (T1:bs) = T2 : (addT as bs)\naddT (T2:as) (T1:bs) = T0 : (addT (addT as bs) [T1])\naddT (T0:as) (T2:bs) = T2 : (addT as bs)\naddT (T1:as) (T2:bs) = T0 : (addT (addT as bs) [T1])\naddT (T2:as) (T2:bs) = T1 : (addT (addT as bs) [T1])\n\nsubT :: TNumber \xe2\x86\x92 TNumber \xe2\x86\x92 TNumber\nsubT a [] = a\nsubT [] b = error "negative numbers supported"\nsubT (T0:as) (T0:bs) = T0 : (subT as bs) \nsubT (T1:as) (T0:bs) = T1 : (subT as bs)\nsubT (T2:as) (T0:bs) = T2 : (subT as bs)\nsubT (T0:as) (T1:bs) = T2 : (subT as (addT bs [T1])) \nsubT (T1:as) (T1:bs) = T0 : (subT as bs)\nsubT (T2:as) (T1:bs) = T1 : (subT as bs)\nsubT (T0:as) (T2:bs) = T1 : (subT as (addT bs [T1]))\nsubT (T1:as) (T2:bs) = T2 : (subT as (addT bs [T1]))\nsubT (T2:as) (T2:bs) = T0 : (subT as bs)\n\nb2t :: BNumber \xe2\x86\x92 TNumber\nb2t [] = []\nb2t [B0] = [T0]\nb2t [B1] = [T1]\nb2t [B0,B1] = [T2]\nb2t [B1,B1] = [T0,T1]\nb2t (b0:b1:b2:bs) = \n   let ts = b2t bs\n       (t0,t1) = conv b0 b1 b2\n   in subT (t0:t1:ts) ts\n   where conv B0 B0 B0 = (T0,T0)\n         conv B1 B0 B0 = (T1,T0)\n         conv B0 B1 B0 = (T2,T0)\n         conv B1 B1 B0 = (T0,T1)\n         conv B0 B0 B1 = (T1,T1)\n         conv B1 B0 B1 = (T2,T1)\n         conv B0 B1 B1 = (T0,T2)\n         conv B1 B1 B1 = (T1,T2)\n

\n\n

[Edit2] subT 的稍微改进版本，不需要 addT

\n\n

subT :: TNumber \xe2\x86\x92  TNumber \xe2\x86\x92  TNumber\nsubT a [] = a\nsubT [] b = error "negative numbers supported"\nsubT (a:as) (b:bs) \n  | b \xe2\x89\xa1 T0 = a : (subT as bs)\n  | a \xe2\x89\xa1 b =  T0 : (subT as bs)\n  | a \xe2\x89\xa1 T2 \xe2\x88\xa7 b \xe2\x89\xa1 T1 =  T1 : (subT as bs)\n  | otherwise = let td = if a \xe2\x89\xa1 T0 \xe2\x88\xa7 b \xe2\x89\xa1 T2 then T1 else T2 \n                in td : (subT as $ addTDigit bs T1)  \n    where addTDigit [] d = [d]\n          addTDigit ts T0 =  ts\n          addTDigit (T0:ts) d = d:ts \n          addTDigit (T1:ts) T1 = T2:ts\n          addTDigit (t:ts) d = let td = if t \xe2\x89\xa1 T2 \xe2\x88\xa7 d \xe2\x89\xa1 T2 then T1 else T0\n                               in td : (addTDigit ts T1)\n

\n