assembly 使用移位和加/减除以常数

4uqofj5v  于 11个月前  发布在  其他
关注(0)|答案(4)|浏览(94)

大家好,我试图除以一个无符号常数只使用移位和加/减-我没有问题,这如果是乘法,但我有点难倒了除法。
例如,假设常数除数是192,被除数是8000
“完整结果”y = 8000/192 = 41(假设我没有保留小数位)
y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62
但如何才能得到更准确的解决方案呢?
多谢了!

zynd9foi

zynd9foi1#

几乎可以肯定有一种更优雅的方法来做到这一点,但这里足以让你开始。
通常这种除法是通过乘以倒数来完成的,即先相乘,然后右移。
(Note:记住乘法可以通过移位和加法来完成(例如n * 3 = (n*2) + (n*1) = (n << 1) + (n) ),但我在这里只使用乘法。你的问题是“移位和加法”,我正在证明我对乘法的速记使用)
在下面的例子中,我试图用一个例子来解释这些概念。

  1. sign(下面使用unsigned int)
    1.溢出(下面我使用32位无符号长整型来保存中间值,但如果你在一个较小的uC上,请注意,相应地进行调整
    1.四舍五入(例如,9/5应该返回1还是2?在C中,它是1,但也许你想要2,因为它更接近正确答案?)
    1.尽可能地(可用位),在除法之前做所有的乘法(最小化截断误差)。再次,要注意溢出。
    正如我所说,阅读下面的内容来理解概念,然后根据您的需求量身定制。
    除以192等于乘以1/192,这与除以(64 * 3)相同。1/3没有精确的(有限的)二进制表示,所以我们用0x 5555/(1 << 16)近似它。
    要除以192,我们除以64,然后除以3。要除以3,我们乘以0x 5555并右移16(或乘以0x 55并>> 8,或...)
//                8000/192          =
//                ((8000/64)/3)     =
//                ((8000 >> 6) / 3) =
//                (((8000 >> 6) * 0x5555) >> 16)
//                (((8000 * 0x5555) >> 22

字符串
请注意,括号是故意的。你想计算(8000 * (0x5555/(1 << 16)),因为第二项是0,乘积将是0。不好。
因此,代码中的一行程序应该是这样的:

printf("Answer:  %lu\n", ((8000UL * 0x5555UL) >> 22));


这将产生41,这是“C”对8000/192的结果,即使42“更接近”。通过检查LSB,如果你想的话,你可以舍入。
人们可以写一篇关于这个主题的论文,但幸运的是**someone much smarter than me already has**。

kjthegm6

kjthegm62#

我开发了一个常数除法生成器,可以很容易地给你给予任何常数的优化除法。它遵循“黑客的喜悦”的想法。
这个名为“kdiv”的工具可以在sourceforge上找到:
http://sourceforge.net/projects/kdiv/

eufgjt7s

eufgjt7s3#

我会看看黑客的喜悦书为这类事情。我没有我的副本与我在一起,但独立的,如果你看看你的除数192,这是0xC 0,所以你可以除以顶部和底部的0x 40,移位8000>>6 = 125. 8000/192 -> 125/3,但是你必须除以3。我们知道答案会在125/2和125/4之间。对于这些特定的数字,125是0x 7 d或b1111101,这是b100000 + 11101的3倍,这是(3次0x 20)+(3乘以8)+ 5,所以125/3 = 0x 20 + 0x 8+(5/3),5/3很快被确定为大于1但小于2,所以0x 28 +1 = 41.只有当除数位模式一直出现在分子位模式的高位时,才继续随着移位而减少。黑客喜悦或其他类似的消息来源说,关于此事,我只是碰巧注意到这些特定的数字的这种模式。

qc6wkl3g

qc6wkl3g4#

如果你把一组降档加起来,你要除以2的非幂。
你如何得到你需要的权力是得到MSB,并将其除以数字,然后这将输出数字与位,你把它们加在一起,得到你需要的除法。
问题是,它需要一个除法来得到这个数字,所以你只能用常数来除法。
有一种方法可以在不使用除法的情况下计算数字,但在硬件上,它看起来与带有条件的除法没有太大的不同或更好,表面上,但我不确定它是更好还是更坏。
但是如果你想做一个变量除法,得到msb,然后乘以你被除数。(所以它需要在开始时相乘,但是你有那些乘法。)
然后再向下移动2
然后检查它是否高于或低于msb,也就是说msb是否作为除法和中的一个分量打开或关闭。
再次向下移动2。
ur要么高于最后一次测试,要么低于最后一次测试这个数字,这取决于你是在最后一次显著性上打开还是关闭组件。
像这样继续下去,你就能算出位移的和除以。
所以它的->
第一个月
ANSWER=(INPUT>>component0)+(INPUT>>component1)+(INPUT>>component2);

相关问题