攤位算法和右移

Question

我知道攤位算法的工作。

假設我們有被乘數M = 01011

和乘法器Q = 01110

我們可以寫爲Q（2^4 - 2^1）。

所以乘法減少到2^4（M）+ 2（-M）

現在亭算法規則是： -

如果Q = 0和Q（-1）= 0然後執行算術右移。

如果Q = 1且Q（-1）= 0，則執行A-M並算術右移。如果Q = 0且Q（-1）= 1，則執行A + M和算術向右移動。如果Q = 1且Q（-1）= 1，則進行算術右移。

這裏A被初始化爲00000和如果我們看到該算法然後在每一步我們做右移位Q（-1）被初始化爲0

。但是根據上面顯示的計算結果是2^4（M）+ 2（-M），我們乘以16和2，這需要左移。

那麼booths算法如何與右移相配合？我無法得到它背後的直覺。

Answer 1

Booth算法的這種變體產生乘法M * Q的最高W位，其中M和Q都有W位。

結果將放在累加器A上，也有W位。也可以恢復低位，特別是在彙編器中，使用SHR acc, 1; RCR low, 1序列。