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

Question

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

take last digit mod 2 -> write down bit

number divide by 2;

在字符串上实现小学部门应该不难,但我认为它效率很低.如果我是对的将是O(l^2),这里l指基10号的长度可以在更快地执行？

Answer 1

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

值 = sum(i in 0...n-1) 10 ⁱ * 数字_i

尽管我不确定您是否可以得出 O(n log n) 算法，但该计算可以以分而治之的方式分为几部分。