下午好，
如果要将一个二进制字符串转换为十进制字符串，而该二进制字符串的字符数超过一种语言中最大整数类型的位数，应该如何操作？换句话说，假设你有这个字符串：
111001101001110100100(...)1001001111011100100
如果你有一个字符串表示的数字，但是不能先将其转换为整数，你该如何编写它的十进制写法？
非常感谢。
6个回答
17
你可以使用以下算法：
// X is the input
while ( X != "0" )
compute X' and R such that X = 10 * X' + R (Euclidean division, see below)
output R // least significant decimal digit first
X = X'
计算X除以10的欧几里得商如下：
R = 0 // remainder in 0..9
X' = ""
for (b in bits of X) // msb to lsb
R = 2*R + b
if R >= 10
X' += "1"
R -= 10
else
X' += "0"
Remove leading "0" from X'
The remainder is R in 0..9
- Eric Bainville
1
这是一个非常好的答案。它适用于任何进制，只需将基数（代码中的10）替换为其他值即可。例如，使用8进行二进制到八进制的转换。 - NealB
5
在十进制下编写自己的算法，只需要加法。以下是Python的示例实现：
from math import log, ceil
def add(a, b):
"""Add b to a in decimal representation."""
carry = 0
for i in range(len(b)):
carry, a[i] = divmod(a[i] + b[i] + carry, 10)
while carry:
i += 1
carry, a[i] = divmod(a[i] + carry, 10)
# an example string
s = bin(3 ** 120)[2:]
# reserve enough decimal digits
res = [0] * int(ceil(len(s) * log(2) / log(10)))
# convert
for c in s:
add(res, res)
if c == "1":
add(res, [1])
#print output
print str.join("", map(str, reversed(res)))
这里使用整数列表表示十进制数字。列表项对应于十进制数字的每一位。索引为0的项对应于个位，索引为1的项对应于十位，以此类推。
- Sven Marnach
4
如果您使用Python 3，它内置了任意长的整数 :) - 9000
1每个Python版本都内置了任意精度整数。我只是使用了Python符号来描述算法。 - Sven Marnach
是的，你总是可以
import decimal，但在Py3k中，普通整数在需要时会迁移到任意精度。顺便说一句，对于这个解释点赞。 - 90001每个版本的Python都内置了任意精度整数，早在“decimal”模块出现之前。上面的代码实际上是使用它们来生成示例字符串（
3 ** 120对于机器精度整数来说太大了）。 - Sven Marnach3
10不是2的幂，因此二进制表示中任何位置的数字都可能影响十进制表示中最低有效位。你必须存储整个十进制表示才能转换比特串。
如果您的语言中找不到长十进制数据类/库，则可以自己构建，这并不难。只需存储足够的十进制数字，例如作为列表，并进行数学计算。对于此任务，您只需要加法，因此实现起来非常容易。
- 9000
2
- T.E.D.
3
1（...）假设（supposing）（...）你不能先将其转换为整数（integer）（...） - Miguel
@Miguel - 一款优秀的大数库应该具备相关实用工具。例如：http://gmplib.org/manual-4.3.2/Formatted-Input-Strings.html#Formatted-Input-Strings - T.E.D.
3您无法将其转换为“机器”整数，但是任意精度的大整数不是机器整数（而且也不需要是整数）。 - 9000
0
假设您没有任意精度的数学包，但您有一组基本的字符串操作例程，则可以执行以下操作：
构建一个2的幂列表，然后通过为字符串中的每个“1”位添加适当的2的幂来逆序拆分二进制字符串。
您需要执行此操作的唯一任意精度算术函数是加法，使用长手算术实现这很容易。
假设您已经实现了一个名为ADD的任意算术加法函数，该函数接受包含十进制数字的2个字符串作为输入，并将十进制和作为字符串返回。类似于：
SumString = ADD(DecimalString1, DecimalString2)
SumString是一个由十进制数字组成的字符串，表示DecimalString1和DecimalString2的和。
步骤1：构建如下的2的幂列表：
BitString is string /* String of '1' and '0' values... */
BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */
PowerOf2 is array of string /* Array of strings containing powers of 2 */
PowerOf2[1] = '1' /* 2**0 to get things started... */
/* Build as many powers of 2 as there are 'bits' in the input string */
for i from 2 to length(BitString) by +1
PowerOf2[i] = ADD(PowerOf2[i-1], PowerOf2[i-1])
end
注意：上述假设数组/字符串是基于1的（而不是基于0的）。
步骤2：拆解BitString并在进行过程中累加总和：
DecimalValue is string /* Decimal value of BitString */
BitString is string /* Your input set of bits as a string... */
ReverseBitString is string /* Reversed input */
DecimalValue = '' /* Result */
BitString = '111001101001110100100(...)1001001111011100100' /* or whatever... */
ReverseBitString = reverse(BitString) /* Reverse so we process lsb to msb */
for i from 1 to length(ReverseBitString) by +1
if substr(ReverseBitString, i, 1) == '1' then /* Bit at position i */
DecimalValue = ADD(DecimalValue, PowerOf2[i])
end
end
if DecimalValue = '' then DecimalValue = '0' /* bit string was all zero */
Display DecimalValue /* This is the result */
如何构建任意精度的
ADD函数？大致如下： function ADD (DecVal1 is string, DecVal2 is string) return string
SumVal is string
Rev1 is string
Rev2 is string
DigitSum is integer
CarryDigit is integer
SumVal = '' /* Result so far... */
Rev1 = reverse(DecVal1) /* Reverse digit order */
Rev2 = reverse(DecVal2) /* Reverse digit order */
/* Pad shorter reversed sting with trailing zeros... */
if length(Rev1) > length(Rev2) then
Rev2 = concat(Rev2, copies(length(Rev1) - length(Rev2), '0')
end
else
Rev1 = concat(Rev1, copies(length(Rev2) - length(Rev1), '0')
end
/* Sum by digit position, least to most significant */
CarryDigit = 0
for i from 1 to length(Rev1) by + 1
DigitSum = CtoI(substr(Rev1, i, 1)) + CtoI(substr(Rev2, i, 1)) + CarryDigit
if DigitSum > 9 then
DigitSum = DigitSum - 10
CarryDigit = 1
end
else
CarryDigit = 0
end
SumVal = concat(ItoC(DigitSum), SumVal)
end
if CarryDigit > 0 then
SumVal = concat(ItoC(CarryDigit), SumVal)
end
return SumVal
假设内置字符串函数：
- reverse(String)：返回反转顺序的字符串
- length(String)：返回给定字符串的长度
- concat(String, String)：返回两个字符串的连接
- substr(String, start, length)：返回从开始到长度字符（基于1）的子字符串
- CtoI(String)：返回给定字符的十进制整数值（例如，'1'= 1，'2'= 2，...）
- ItoC(Integer)：返回整数的十进制字符表示形式（例如，1 ='1'，2 ='2'，...）
- copies(count, string)：返回字符串的count个拼接副本
- NealB
0
给你...
void toBCD1( char *p ) {
const int decSize = 120; // Arbitrary limit of 10^119.
static binByte decDgt[ decSize ]; // decimal digits as binary 'nibbles'.
int curPow10 = 0;
memset( decDgt, 0, sizeof(decDgt) );
for( char *cp = p; *cp; cp++ ) {
for( int ii = curPow10; ii >= 0; ii-- ) {
if( decDgt[ ii ] >= 5 ) // Algorithm step
decDgt[ ii ] += 3;
decDgt[ ii ] <<= 1;
if( decDgt[ ii ] & 0x10 ) { // Carry high bit?
decDgt[ ii + 1 ] |= 0x1;
if( ii == curPow10 ) // new power of 10?
curPow10++;
decDgt[ ii ] &= 0xF; // dealing in 'nibbles'
}
}
decDgt[ 0 ] |= ( *cp == '1' ); // truth value 0 or 1
}
for( int ii = curPow10; ii >= 0; ii-- )
putchar( decDgt[ ii ] + '0' );
putchar( '\n' );
}
void demo_toBCD( void ) {
char *bp = "11100110"
"10011101"
"00100100"
"10011110"
"11100100"
"01001001"
"11101110"
"01000100"
"10011110"
"11100100";
toBCD1( bp );
}
- Fe2O3
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接