以表示十进制数s="556852144786"
n=556852144786
为例。有没有直接算法将其转换为s1="1000000110100110..."
1000000110100110...
是n
的二进制表示?
我假设您正在寻找一种直接对字符串进行操作的算法,而不是转换为目标语言支持的任何整数并使用这些整数?
有多种方法可以做到这一点。这里有两个,但如果你眯着眼睛足够用力,它们几乎是相同的算法。
方法一:重复将十进制字符串除以二
在这种方法中,我们反复将原始十进制字符串除以 2(使用十进制算术),并跟踪余数:这些余数以相反的顺序为您提供结果的位。 这是该算法在Python中的样子。它缺少is_nonzero
和divide_by_two
的定义。我们稍后会提供这些。
def dec_to_bin(s):
"""
Convert decimal string s to binary, using only string operations.
"""
bits = ""
while is_nonzero(s):
s, bit = divide_by_two(s)
bits += bit
# The above builds up the binary string in reverse.
return bits[::-1]
该算法以相反的顺序生成位,因此我们需要一个最终的反向来给出生成的二进制字符串。
divide_by_two
函数接受一个十进制字符串s
并返回一个新的十进制字符串,表示商s / 2
,以及余数。其余部分是单个位,再次表示为字符串 -"0"
或"1"
。它遵循通常的逐位数字学校教授的从左到右划分方法:每一步涉及将一位数以及上一步带来的进位除以二。这是该函数:
def divide_by_two(s):
"""
Divide the number represented by the decimal string s by 2,
giving a new decimal string quotient and a remainder bit.
"""
quotient = ""
bit = "0"
for digit in s:
quotient_digit, bit = divide_digit_by_two(bit, digit)
quotient += quotient_digit
return quotient, bit
我们剩下需要定义divide_digit_by_two
,它取一个位数加上一个十进位,然后除以 2 得到一个数字商和一个单位余数。此时,所有输入和输出都是长度为 1 的字符串。在这里,我们作弊并使用整数算术,但只有 20 种可能的不同输入组合,因此我们可以很容易地使用查找表来代替。
def divide_digit_by_two(bit, digit):
"""
Divide a single digit (with tens carry) by two, giving
a digit quotient and a single bit remainder.
"""
digit, bit = divmod(int(bit) * 10 + int(digit), 2)
return str(digit), str(bit)
您可以将divide_digit_by_two
视为交换不同基数的两个数字的原始算术运算:它将小于20
以10 * bit + digit
形式表示的非负整数转换为以2 * digit + bit
形式表示的相同值。
我们仍然缺少一个定义:is_nonzero
的定义。十进制字符串表示零,当且仅当它完全由零组成。这是一个快速的Python测试。
def is_nonzero(s):
"""
Determine whether the decimal string s represents zero or not.
"""
return s.strip('0') != ''
现在我们已经准备好了所有位,我们可以测试:
>>> dec_to_bin("18")
'10010'
>>> dec_to_bin("556852144786")
'1000000110100110111110010110101010010010'
>>> format(556852144786, 'b') # For comparison
'1000000110100110111110010110101010010010'
方法2:重复将二进制字符串乘以10
这是第一种方法的变体:我们不是重复除法,而是逐个数字(从左到右)处理传入的十进制字符串。我们从一个表示值的空二进制字符串开始0
,每次我们处理一个数字时,我们乘以 10(在二进制表示中)并添加该数字表示的值。和以前一样,最方便的是按小端顺序(首先是最低有效位)构建二进制字符串,然后在末尾反转以获得传统的大端表示。下面是顶级函数:
def dec_to_bin2(s):
"""
Convert decimal string s to binary, using only string operations.
Digit-by-digit variant.
"""
bits = ""
for digit in s:
bits = times_10_plus(bits, digit)
return bits[::-1]
times_10_plus
函数的工作是获取一个二进制字符串和一个数字,并生成一个新的二进制字符串,表示将原始值乘以 10 的结果,并将二进制数字的值相加。它看起来像这样:
def times_10_plus(bits, digit):
"""
Multiply the value represented by a binary string by 10, add a digit,
and return the result as a binary string.
"""
result_bits = ""
for bit in bits:
digit, result_bit = divide_digit_by_two(bit, digit)
result_bits += result_bit
while digit != "0":
digit, result_bit = divide_digit_by_two("0", digit)
result_bits += result_bit
return result_bits
请注意,我们使用与以前完全相同的算术原语divide_digit_by_two
,但现在我们的想法略有不同:它将一个位乘以十,添加一个进位数字,并将其转换为一个新位(结果的最低有效位)以及一个新的进位数字。
效率说明
为了清楚起见,我留下了一些 Python 级别的低效率。特别是,在构建字符串时,构建位或数字列表,然后在末尾与str.join
操作连接会更有效。另请注意,根据实现语言的不同,就地修改数字字符串或位字符串可能更有意义,而不是在每个步骤中生成新字符串。我把必要的修改留给你。