将长数字从 base-256 转换为 base-255 并返回时是否有快捷方式或特殊情况？

Question

我有很多大数字，有几百个字节长。

如何有效地将它们从基数 256 转换为基数 255，使数字最多长一个字节，但在任何输出字节中不使用值（或数字）0xFF？

（我已经编写了一个通用解决方案，但它的复杂度为 O(n*n)，因为每个输入数字都会影响许多输出数字。）

将长数字从 base-256 转换为 base-255 并返回时是否有快捷方式或特殊情况？

Answer 1

为了加快速度，您需要考虑更大的基地。

第一步是将原始的“base 256”转换为“base 1<<32”或“base 1<<64”（取决于您的 CPU 是什么）。这会将号码中的位数减少 4（或 8）倍。如果字节顺序（“endianess”）兼容并且“字节长度”是 8 的倍数（这在早期代码中应该很容易确保），这可能涉及实际上不执行任何操作（类型转换和严格的别名规则会带来一些麻烦）在变成零字节机器代码的源代码中）。

以相关的方式；您可以先转换为“base 255*255*255*255”，而不是直接转换为“base 255”；然后将每个“大数字”拆分为一对较小的“基数 255*255”数字，然后将它们拆分为较小的“基数 255”数字。使用 SIMD（同时分割多个数字），这种分割可以非常快。

这些更改应该使其速度提高近 16 倍。本质上，如果您的除法算法是“O(n*n)”，它将变成“O(n/4 * n/4)”或“O(n*n/16)”。当然，“O(n*n/16)”被认为与“O(n*n)”相同，尽管速度要快得多。