c++ - 在 C/C++ 中将非常大的 int（写为字符串）转换为二进制字符串

Question

我有一个以 10 为基数的数字，大约有 10k 位。我想将其转换为基数 2（1010101001 ...）。我能想到的只是原始算法：

take last digit mod 2 -> write down bit

number divide by 2;

在字符串上实现小学除法应该不难，但我认为它非常低效。如果我是对的，它将是O(l^2)，其中l表示以 10 为基数的数字长度。可以更快地完成吗？

Answer 1

除以 2 与乘以 1/2 相同。对于后者，您可以使用一些众所周知的快速乘法算法（Toom–Cook、Schönhage–Strassen 等）。

Answer 2

如果您正在处理大数字，我真的建议您使用多精度库。尝试 GMP 或 MPRF 或类似的东西。
-Øystein

Answer 3

据我了解，您的大数表示为十进制数字序列。如果是这样，您可以使用乘法和加法计算“二进制”表示：

value = sum(i in 0...n-1) 10 ⁱ * digit _i

这种计算可以以分而治之的方式分成几部分，尽管我不确定你是否可以达到 O(n log n) 算法。