這是一個關于演算法的概念性問題，與我個人正在解決的問題有關。
任何有用的 CPU 架構在乘法后將溢位位存盤在某個暫存器中，但如果此功能不可用怎么辦？有沒有一種有效的方法來計算溢位位？
因為它是溢位 a * b >> bits不是一種選擇。
uj5u.com熱心網友回復：
我可以想象兩個基本選項。
舊的 CPU 根本不支持乘法。我們不得不手動完成。您始終可以通過加法和移位來實作乘法。該演算法非常簡單，并且不限于任意數量的位（因為在所有 CPU 上的任意數量的位中都可以輕松實作加法和移位）。
如果您的 CPU 可以在 N 位不溢位的情況下進行乘法，您可以使用它作為幫助器，比上面提到的逐位計算更快地獲得結果。如果 a 和 b 均為 N 位寬，則 a * b 的結果為 2N 位寬。如果你將 a 和 b 分成兩半，那么每一半都是 N/2 寬，它們的乘積是 N 位寬。因此，您將一半彼此相乘，然后將它們加在一起。如果我們標記上半部分a2/b2和下半部分a1/b1，那么下半部分結果是a1 * b1，中間結果是a2 * b1 a1 * b2，上半部分結果是a2 * b2，每次加上溢位。我希望它足夠瑣碎，因此不需要詳細描述。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400686.html
上一篇：排序陣列中的二分查找
下一篇：排序陣列中元素的天花板