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

Question

我有一个基数为 10 的数字，大约有 10k 位。我想将它转换成基数 2 (1010101001...)。我能想到的就是原始算法:

取最后一位 mod 2 -> 记下位

数字除以 2;

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

Answer 1

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

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

此计算可以分而治之的方式拆分成多个部分，但我不确定您是否可以得出 O(n log n) 算法。