我收到一个基于 2^k 的非常大的数字列表(k<=30,数字数量<=10^7)。
我需要做的是获取两个数字(我们称它们为 X 和 Y),将它们相减(A=X-Y,B=Y-X)并返回 A 和 B 的二进制表示。
我当前的代码如下所示:
k = int(input())
base = pow(2, k)
numbersX = stdin.readline().split()
digitsX = len(numbersA) - 1
x = 0
i = 1
while i <= digitsX:
factor = pow(base, digitsX - i)
x += int(numbersX[i]) * factor
i += 1
(与 Y 类似)
我只是简单地将收到的数字转换为小数,然后减去并得到二进制表示。它有效但速度很慢。您会建议其他解决方案吗?
Sample input:
4 (for k)
6 15
2 7
So X = 6 15 = 6*16^1 + 15*16^0 = 96 + 15 = 111 (decimal)
Y = 2 7 = 2*16^1 + 7*16^0 = 32 + 7 = 39 (decimal)
A = X – Y = 111 – 39 = 72
B = Y – X = 39 – 111 = -72
Output:
01001000 (A in SM binary)
10111000 (B in U2 binary)
最佳答案
这是一种将任何基数的数字转换为整数的方法:
def to_int(digits, base=1024):
place = 1
ret = 0
for digit in reversed(digits):
ret += place*digit
place *= base
return ret
如果您的基数始终是 2 的幂 (2^10 = 1024
),您也可以这样做(可能效率更高):
def to_int2(digits, log2base=10):
ret = 0
for digit in digits:
ret <<= log2base
ret += digit
return ret
然后将其表示为二进制字符串,您可以这样做:
print('{:0b}'.format(to_int(digits=(981, 5, 0, 1001))))
print('{:0b}'.format(to_int2(digits=(981, 5, 0, 1001))))
两者的结果相同(我假设最左边的是最重要的“数字”;否则您将不得不反转
“数字”的顺序):
1111010101000000010100000000001111101001
(读取输入和减法应该是直截了当的。)
对于您添加的示例,它会像这样工作:
x = to_int2(digits=(6, 15), log2base=4)
y = to_int2(digits=(2, 7), log2base=4)
print(x, y) # 111 39
diff = x-y
print('{:08b}'.format(diff)) # 01001000
print('{:08b}'.format(-diff & 0xff)) # 10110111
如果你需要动态获取格式和掩码,你可以尝试这样的事情:
d = 111-39
bit_length = max(int.bit_length(d), int.bit_length(-d))
fmt = '{{:0{}b}}'.format(bit_length+1)
mask = (1<<bit_length+1) - 1
print(fmt.format(d))
print(fmt.format(-d & mask))
不确定这是否正确涵盖了所有边缘情况...但我相信您从那里就明白了!
关于python - 在不同基础上对非常大的数字执行操作的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43640466/