在不同基地中對非常大的數字執行操作的最快方法

我收到非常大的2^k數字的數字列表（k < = 30，數字量< = 10^7）。在不同基地中對非常大的數字執行操作的最快方法

我需要做的是讓兩個數字（我們姑且稱之爲X和Y），減去他們（A = XY，B = YX）並返回的二進制表示和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)

來源

2017-04-26 MuchaZ

' '{：04B}'。格式（5）＃0101'給出的二進制表示（如'str'）零填充以具有4'的長度0b10010101'（或'int（'10010101'，2）'）是由該位序列表示的整數......您不必爲任何這些操作而循環。 –

@hiroprotagonist，我不知道你是否正確理解我。我收到具有4位數字的1024位數字，樣本輸入：981 5 0 1001.如何將此數字轉換爲二進制數？ – MuchaZ

這不是一個完整的答案。但是，是的，我並沒有真正不喜歡。你的代碼也不完整。什麼是'基地'？輸入和期望輸出的例子將會很有幫助。 –

這是數字轉換成任何基地爲整數的方式：

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))))

結果是相同的兩個（我假設最左邊是最重要的'數字';否則，你將不得不reverse的「數字」）的順序：

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))

不知道是否能正確覆蓋所有的邊緣情況......但我相信你從這裏得到它的權利！

來源

2017-04-26 17:27:42

這很完美，謝謝你的幫助！ :) 還有一個問題：如何處理更大數字的情況下的0xff？我的意思是如何「動態」使用例如0xfffff等等？ – MuchaZ

@MuchaZ試圖爲「動態格式」添加內容。希望有所幫助。 –

你可以消除pow

x = 0 
i = 1 
while i <= digitsX: 
    x *= base 
    x += int(numbersX[i]) 
    i += 1

來源

2017-04-26 17:27:47

在不同基地中對非常大的數字執行操作的最快方法

回答

相關問題