将非常大的数字转换为基数10字符串
一个整数测量4个字节。 在我的例子中，我的数字为1 MB。 如何快速将它们转换为人类可读的十进制数？
该数字出现在包含Size项的uint[]数组中。
我不知道这是否更快，但这里是delphi中的一个例子，我很久以前写过把大字符串作为字符串处理（非常快速和脏） – 这是128bit uint但你可以无限延长
Function HexToBinShort(hex:integer):string; begin case hex of 0: result:='0000'; //convert each hex digit to binary string 1: result:='0001'; //could do this with high-nybble and low nybble 2: result:='0010'; //of each sequential byte in the array (mask and bit shift) 3: result:='0011'; //ie: binstring:=binstring + HexToBinShort(nybble[i]) 4: result:='0100'; //but must count DOWN for i (start with MSB!) 5: result:='0101'; 6: result:='0110'; 7: result:='0111'; 8: result:='1000'; 9: result:='1001'; 10: result:='1010'; 11: result:='1011'; 12: result:='1100'; 13: result:='1101'; 14: result:='1110'; 15: result:='1111'; end; end;
然后取出连接的二进制字符串，每次看到’1’时加上2的幂
Function BinToIntString(binstring:string):string; var i, j : integer; var calcHold, calc2 :string; begin calc2:=binstring[Length(binstring)]; // first bit is easy 0 or 1 for i := (Length(binstring) - 1) downto 1 do begin if binstring[i] = '1' then begin calcHold:=generateCard(Length(binstring)-i); calc2 := AddDecimalStrings(calcHold, calc2); end; end; result:=calc2; end;
generateCard用于创建2 ^ i的十进制字符串表示（对于i> 0）
Function generateCard(i:integer):string; var j : integer; var outVal : string; begin outVal := '2'; if i > 1 then begin for j := 2 to i do begin outVal:= MulByTwo(outVal); end; end; result := outVal; end;
和MulByTwo将十进制字符串乘以2
Function MulByTwo(val:string):string; var i : integer; var carry, hold : integer; var outHold : string; var outString :string; var outString2 : string; begin outString:= StringOfChar('0', Length(val) + 1); outString2:= StringOfChar('0', Length(val)); carry :=0; for i := Length(val) downto 1 do begin hold := StrToInt(val[i]) * 2 + carry; if hold >= 10 then begin carry := 1; hold := hold - 10; end else begin carry := 0; end; outHold := IntToStr(hold); outString[i+1] := outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end;
最后 – AddDecimalStrings ……好吧，它添加了两个十进制字符串：
Function AddDecimalStrings(val1, val2:string):string; var i,j :integer; var carry, hold, largest: integer; var outString, outString2, bigVal, smVal, outHold:string; begin if Length(val1) > Length(val2) then begin largest:= Length(val1); bigVal := val1; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val2) +1) to largest do begin smVal[i] := val2[j]; j:=j+1; end; end else begin if length(val2) > Length(val1) then begin largest:=Length(val2); bigVal:=val2; smVal := StringOfChar('0', largest); j:=1; for i := (largest - length(val1) +1) to largest do begin smVal[i] := val1[j]; j:=j+1; end; end else begin largest:=length(val1); bigVal:=val1; smVal:=val2; end; end; carry:=0; outString:=StringOfChar('0', largest +1); outString2:=StringOfChar('0', largest); for i := largest downto 1 do begin hold := StrToInt(bigVal[i]) + StrToInt(smVal[i]) + carry; if hold >=10 then begin carry:=1; hold := hold - 10; end else begin carry:=0; end; outHold:= IntToStr(hold); outString[i+1]:=outHold[1]; end; if carry = 1 then begin outString[1] := '1'; result := outString; end else begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result := outString2; end; end;
这些函数允许您对几乎任意大的整数执行基本算术作为字符串。 当然，当数字位数太大而无法索引数组时，你会碰到另一面墙。
这是一个除以二，顺便说一句（对于另一种方式很有用……）。 我这里不处理奇数。
Function DivByTwo(val:string):string; var i : integer; var hold : integer; var outHold : string; var outString, outString2 :string; begin outString:=StringOfChar('0',Length(val)); for i := Length(val) downto 1 do begin if StrToInt(val[i]) mod 2 = 0 then begin hold:= Math.Floor(StrToInt(val[i]) / 2); outHold:= IntToStr(hold); outString[i]:=outHold[1]; end else begin hold:= Math.Floor((StrToInt(val[i]) - 1) / 2); outHold:=IntToStr(hold); outString[i]:= outHold[1]; if i <> Length(val) then begin hold:= StrToInt(outString[i+1]) + 5; outHold:= IntToStr(hold); outString[i+1] := outHold[1]; end; end; end; outString2:=StringOfChar('0',Length(val)-1); if (outString[1] = '0') and (length(outString) > 1) then begin for i := 1 to length(outString2) do outString2[i]:=outString[i+1]; result:=outString2; end else begin result:=outString; end; end;
编辑：我刚用一个900万位长的二进制字符串尝试了这个，它非常慢！ 真的，这并不奇怪。 这是一个完全未经优化的代码，它有很多低成本可供选择，以加快速度。 尽管如此，我还是忍不住觉得这是你可能想要在完全优化的assembly中编写的问题的种类（或规模）。 个别操作很小但是必须多次完成 – 这些咒语要求组装。 multithreading当然也可以在这里使用。
我一直在考虑你的问题。 我没有编写解决方案，但这是一种方法：
首先，让我们假设你有一个2 n位的集合而不失一般性。 （如果你的位数少于2 n ，则用前导零填充位数组，直到你这样做。显然这样做的时间绝对不会超过数组的大小。）在你的情况下，你说你有一百万的uint，所以这是2 25位。
我们还假设每个2 k + 1位的集合可以均匀地分成两个位集合，左右集合，每个集合有2 k位。
因此，每个比特集合或子集合具有“大小”，其是2的精确幂。 最小的集合包含一个位，无法进一步细分。
其次，我们假设您同样具有十进制forms的数字的不可变表示，并且再次，在不失一般性的情况下，字符串中有2个d十进制数字。 如果少于2 d ，则再次使用前导零填充。 同样，每个大于1的小数集合可以分成两个集合，每个集合大小只有一半。
现在我们勾勒出一个递归算法：
DigitCollection Convert(BitCollection bits) { if (bits.Size == 1) return bits[0] ? DigitCollection.SingleOne : DigitCollection.SingleZero; DigitCollection left = Convert(bits.Left); DigitCollection right = Convert(bits.Right); DigitCollection power = MakePowerOfTwo(bits.Right.Size); return Add(Multiply(left, power), right); }
我们现在需要方法Add，Multiply和MakePowerOfTwo。 正如我们稍后将看到的，我们还需要Subtract和两个Shift运算符，以便快速乘以10的幂。
加法和减法很容易。 显然，如果较长的集合包含n个数字，则可以实现加法和减法方法以花费O（n）时间。
FullShift和HalfShift运算符从旧的数字集合中创建新的数字集合，以便于以10的幂进行快速乘法。 如果大小为2 d + 1的数字集合由每个大小为2 d的子集合（X1，X2）组成，那么“半移”集合包含2 d + 2项并且由（（2 d前导零，X1）组成），（X2,2 d尾随零））。 全class集合包括（（X1，X2），（2 d + 1尾随零））。
这些显然非常便宜。
乘法是我们遇到大问题的地方 。 假设在不失一般性的情况下，我们将两个DigitCollections相乘，每个DigitCollections正好有2个数字。 我们可以使用Karatsuba的算法：
DigitCollection Multiply(DigitCollection x, DigitCollection y) { // Assume x and y are the same digit size. if (x and y are both single digits) return the trivial solution; // Assume that z2, z1 and z0 are all the same digit size as x and y. DigitCollection z2 = Multiply(x.Left, y.Left); DigitCollection z0 = Multiply(x.Right, y.Right); DigitCollection z1 = Subtract( Multiply(Add(x.Left, x.Right), Add(y.Left, y.Right)), Add(z2, z0)); return Add(Add(FullShift(z2), HalfShift(z1)), z0); }
这个算法的顺序是什么？ 假设有n = 2个d位数。 什么是O（乘（n））？ 我们递归三次，每次都有一半的数字问题。 其余的加，减和移位操作都不超过O（n）。 所以我们有一个复发：
T(n) = 3 T(n/2) + O(n)
通过主定理有一个简单的解决方案：这个算法是O（n 1 / lg 3 ），大约是O（n 1.58 ）。
MakePowerOfTwo怎么样？ 鉴于我们已经拥有的东西，这很容易。 我们使用身份：
2 2n + 1 = 2 n x 2 n + 2 n x 2 n
并编写算法：
DigitCollection MakePowerOfTwo(int p) { if (p == 0) return DigitCollection.SingleOne; DigitCollection power = MakePowerOfTwo(p / 2); power = Multiply(power, power); if (p % 2 != 0) power = Add(power, power); return power; }
它由乘法的计算决定，O（n 1.58 ）也是如此。
现在我们可以看到转换的原始调用也由乘法控制。
因此，如果您有2 d二进制数字进行转换，使用此算法，您可以预期这将需要大约O（2 1.58 d ）步骤。 在你的情况下你有2 25位转换，所以这应该需要大约7,770亿计算。
这里的关键事实是该算法完全由乘法的成本支配 。 如果你可以将乘法的成本降低到小于O（n 1.58 ），那么你将获得巨大的胜利。 如果我是你，我将研究对Karatsuba的十进制乘法算法的改进。
您可以通过一次执行多个数字来节省一些时间。 如果你这样做，比如说，每次100,000，那么它一次可能至少比10快一点。
请注意，它仍然可能非常缓慢，但它会为您节省一些时间。
可以想象你可以使它递归，并加快它的速度 – 获得数字的粗略平方根，向下舍入到最接近的10. div和mod的指数，并将结果发送回相同的function。 请注意，我不确定你如何有效地运行那个大小的div或mod，但是如果你能弄明白（并且不会耗尽内存），它仍然必然会更加节省时间而不是一次将其分成一个数字。
替代版本：放弃小数 – 因为数字太大而无法理解任何真正的人类读者 – 并以hex呈现。 技术上仍然是人类可读的，但你可以一次渲染一个字节，为自己省去了很多心痛。
谢谢大家，我想出了一种主要基于J …的想法，他建议将数字转换为10个基数，每次加1时加2的幂。 但是我使用基于1000000000000000000（10 ^ 18）的系统而不是基于10的（人类十进制系统）。 所以每个数字不仅有10个可能性（0 … 9），实际上10 ^ 18！ 这适用于我们随后转换的64位数字.ToString()
这是最有效的方式。