8

是否有人知道（或可能指向某些来源以阅读）将二进制数字系统表示的数字转换为三进制数字系统（我的特殊情况）的方法或算法，或用于此类转换的通用算法？

我已经实现的解决方案是先将数字转换为十进制，然后将其转换为所需的数字系统。这可行，但有两个步骤。我想知道是否可以在不先实现三进制算术的情况下轻松一步完成？有什么诀窍吗各位？

UPD：我似乎没有设法清楚地描述我正在寻找哪种转换方式。我不是在要求某种将base-2转换为base-3的方法，我确实知道如何做到这一点。您可能会认为我有用于三进制和二进制数的代数数据结构，在 Haskell 中它看起来像这样：

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

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

有两种明显的方法可以将一个转换为另一个：首先将其转换为 Integer 并获得结果（不是有趣的方法），第二个是在 base-3 中实现自己的乘法和加法，并将结果乘以数字值计算为两个的各自力量（直截了当和沉重）。

所以我想知道除了这两种方法之外是否还有另一种方法。

4

9 回答 9

6

如果你用计算机做这件事，事情已经是二进制的，所以只需反复除以 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

于 2010-08-03T20:21:52.207 回答
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)
于 2010-08-04T06:45:28.740 回答
3

我认为每个人都缺少一些重要的东西。首先，预先计算一个表，对于每个二进制位，我们需要以三进制表示。在 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 为基数的表示形式。现在你需要做的就是做carry。从个位数开始。

5 大于 2，因此减去 3 的倍数，并酌情增加结果的第二位。

0013322

第二个数字现在是 2，一个合法的三进制数字，所以继续第三个数字。也随身携带，

0014022

最后产生现在完全有效的三进制数......

0021022

我的计算正确吗？我会让 MATLAB 为我们做出最终判断：

base2dec('011000101',2)
ans =
   197

base2dec('0021022',3)
ans =
   197

我有没有指出这个操作是多么微不足道，我可以完全手动进行转换，基本上直接从二进制到三进制，至少在我写下并存储了初始表之后？

于 2010-08-04T10:25:35.187 回答
1

恐怕我对 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）来实现

于 2010-08-04T09:46:15.193 回答
0

如果这是家庭作业，请使用伪代码向后编写x基础：b

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

我相信您可以弄清楚如何将结果向前而不是向后写入。请注意，/需要进行 C 风格的整数除法（结果是整数，向零截断）。

请注意，这根本不取决于执行算术的基数。算术是在整数上定义的，而不是在特定基数中整数的表示。

编辑：根据您更新的问题，我会将数字表示形式转换为整数（通过 ors 和 shifts），并使用上述算法和整数算术。

当然，您可以按照您的描述进行操作，但这似乎是一项非常艰巨的工作。

于 2010-08-03T20:45:31.307 回答
0

我不认为有一个超级有效的方法。

“我已经实施的解决方案是先将数字转换为十进制。”

我假设您实际上是首先转换为某些内置整数类型。我不认为内置整数与以 10 为底有任何关系。（虽然，当你打印它时，会有一个以 10 为底的转换）。

也许您希望有一些算法可以一次查看输入一位数并产生输出。

但是，假设您要将 3486784400（以 10 为底）转换为以 3 为底。您需要在生成输出之前检查每个数字，因为

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

..还

“计算结果将数字值乘以各自的 2 次方”

不需要显式计算幂，请参阅从以 60 为基数转换为以 10 为基数

于 2010-08-03T21:14:51.177 回答
0

我认为这个问题可能有一些不同的“观点”，尽管我不确定它们中的任何一个更快或更好。例如，n 的低位 3 位数字只是 n mod 3。假设您已经有了 n 的二进制表示。然后考虑 2 的幂如何计算出 mod 3。 2^0 = 1 mod 3, 2^1 = 2 mod 3, 2^2 = 1 mod 3, 2^3 = 2 mod 3, ... 换句话说，幂在 1 mod 3 和 2 mod 3 之间交替。您现在可以通过扫描 n 的二进制表示并且通常只在每个位位置添加 1 或 2 来获得低位基数 3 数字出现 1 的地方。

于 2010-08-04T01:51:39.340 回答
0

不，您不能将 base2 数字转换为 base3 数字而不将其加载到整数中。原因是 2 和 3 互质——它们没有公因数。

如果您使用的是 base2 和 base4，甚至是 base6 和 base9，那么直到两个基数的最小公倍数的整数集将由两个同构集表示。例如 13 (base4) = 0111 (base2)，所以转换 1313 (base4) = 01110111 (base2) - 这是一个查找和替换操作。

至少您拥有的解决方案有效并且相对简单。如果您需要提高性能，则在开始 base3 转换之前将整个 base2 表示转换为整数；这意味着更少的模运算。另一种方法是逐个处理 base2 数字中的每个字符，在这种情况下，您将除以 base2 表示中每个数字的所有 3 的幂。

于 2010-08-04T09:59:09.820 回答
0

如果您使用二进制编码的三进制（每个三位的一对位），您可以使用并行算术进行转换。请参阅本教程。

于 2020-05-25T15:09:28.480 回答