algorithm - 高效的基数 2 到基数 5 的转换

Question

有没有什么方法可以有效地将二进制字符串或文件转换为基数 5，而不必将所有位作为数字存储在一个 var 中？
例如对于 base64，您可以将 log2(64)=6 位组成一组。

编辑:感谢您的回答，但我会再次提及这一点:该算法应该适用于文件。如果文件太大以至于无法存储在单个 int 变量中，那么执行通常的 n % base 转换就没有任何好处。

Answer 1

假设您必须在内存中存储最终数字的表示，我们可以有 O(n * d) 时间，O(d) 空间，其中 n 是原始数字中的位数，d 是转换后数字中的位数，通过一系列以 5 为底的加法，保持当前的幂2 以 5 为基数(其中我们最多添加一个)和结果。小的优势是通过长乘模 5 从前一个生成下一个 power-of-2-in-base-5:

44(10)
101100(2)

power-of-2-in-base-5, result
1, 0
2, 0
4, 4
13, 22
31, 22
112, 134

就它可能提供任何加速而言，我们可以通过查表避免实际的乘法和加法运算，因为两个操作数模 5 的每个运算符只有 25 种组合。