存儲M個n位二進制數的總和的最大位寬

我試圖找到公式來計算包含M個n位無符號二進制數的總和所需的最大位寬。謝謝！存儲M個n位二進制數的總和的最大位寬

來源

2017-06-14 bfung

好，如果我添加了兩個它可能需要長達兩個位一個位數字。如果我添加兩個兩位數字，最糟糕的情況是需要三個位數來翻轉。如果我添加兩個三位數最壞的情況下需要四個... –

如果我添加1111與四位和1位，它需要五個結果。沒有不同於小數點後兩位數字的數字可能需要兩位數的結果，依此類推。 –

所需的最大位寬應爲 ~~ceil(log_2(M * (2^n - 1)))~~ 。

編輯：感謝@MBurnham我現在意識到它應該是floor(log_2(M * (2^n - 1))) + 1而不是。

來源

2017-06-14 02:02:16 xunatai

嗯......我用wolfram alpha實驗測試了兩個公式......好像有些東西還沒有關閉...... – bfung

@bfung關如何？ – xunatai

例如，對於M = 9和n = 3，您提出的公式將給出7.當我在wolfram alpha中添加0b111 9次時，答案= 6b111111。 – bfung

假設爲正整數，您需要floor（log2（x））+1位來存儲x。並且m個n位數的總和可以產生的最大值將是m * 2^n。所以我相信公式應該是

floor(log2(m * 2^n)) + 1

位。

來源

2017-06-14 02:17:20 MBurnham

最大的n位數是2^n-1，而不是2^n – mbschenkel

@mbschenkel只有1個數字是正確的，但當您有兩個數字的總和時，可以將數值轉移到下一個數字。所以你需要存儲一個額外的位來進行轉賬 – MBurnham

你已經在用'm'來處理這個問題了。如果'B = 2^n-1'是1的最大可能值，那麼'm * B'是'm'加數的最大可能和，而不是'm *（B + 1）'。 – mbschenkel

如果我添加2個數字，我需要比2個數字中較寬的一個多1位來存儲結果。所以，如果我添加2個n位數，我需要n + 1個位來存儲結果。

if I add another n-bit number, I need (n+1)+1   bits to store the result (that's 3 n-bit numbers added so far) 
if I add another n-bit number, I need ((n+1)+1)+1  bits to store the result (that's 4 n-bit numbers added so far) 
if I add another n-bit number, I need (((n+1)+1)+1)+1 bits to store the result (that's 5 n-bit numbers added so far)

所以，我覺得你的公式是

n + M - 1

來源

2017-06-14 08:48:58

這是一個上限，但不一定是最小需求（儘管OP要求最大...）。添加兩個數字時，不要使用全部範圍：例如1 + 1 = 10，而不是11,1 + 1 + 1 = 11，並且根本不使用第3位。儘管如此，這對兩個補碼負數是不同的。 – mbschenkel

存儲M個n位二進制數的總和的最大位寬

回答

相關問題