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

Question

嗨所有我试图除以无符号常数除以仅使用移位和加/减 - 如果它是乘法我没有问题,但我有点被分裂困扰.

例如,假设常数除数为192,可以说红利为8000

"完整结果"y = 8000/192 = 41(假设我没有保留小数位)

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

但是,我如何获得更准确的解决方案？

非常感谢!

Answer 1

几乎可以肯定有一种更优雅的方式,但这足以让你开始.

通常以这种方式划分是通过乘以倒数来完成的,即,第一乘法然后右移.

(注意:请记住,乘法可以通过移位和添加来完成(例如,n * 3 = (n*2) + (n*1) = (n << 1) + (n) )但我只是在这里使用乘法.你的问题说"移位和补充",我正在证明我的速记使用乘法)

在下面的例子中,我试图用一个例子来解释这些概念.在您的具体情况下,您将需要考虑诸如此类的问题

1. 标志(我在下面使用无符号整数)

2. 溢出(下面我使用的是32位无符号长整数来保存中间值但是如果你在较小的uC上注意,请相应调整

3. 舍入(例如,应该9/5返回1或2？在C中,它是1,但也许你想要2因为它更接近正确的答案？)

4. 在你可以(可用位)的范围内,在你的除法之前做你所有的乘法(最小化截断错误).再次,请注意溢出.

正如我所说,阅读以下内容以了解概念,然后根据您的需求量身定制.

除以192与乘以1/192相同,这与除以(64*3)相同.没有1/3的精确(有限)二进制表示,所以我们用0x5555 /(1 << 16)逼近它.

要除以192,我们除以64然后除以3.除以3,我们乘以0x5555并向右移16(或乘以0x55和>> 8,或......)

//                8000/192          =
//                ((8000/64)/3)     =
//                ((8000 >> 6) / 3) =
//                (((8000 >> 6) * 0x5555) >> 16)
//                (((8000 * 0x5555) >> 22

请注意,括号是故意的.你不希望计算(8000 * (0x5555/(1 << 16)),因为第二项为0,该产品将是0不好.

因此,代码中的1行代码将类似于:

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

这将产生41,这就是"C"会产生的8000/192,即使42"更接近".通过检查LSB,您可以根据需要进行舍入.

人们可以写一篇关于这个主题的论文,但幸运的是,比我已经聪明的人已经有了.

Answer 2

我开发了一个常数除法生成器，可以轻松地为您提供任何常数的优化除法。它遵循“黑客的喜悦”的想法。

名为“kdiv”的工具可在 sourceforge 获得：

http://sourceforge.net/projects/kdiv/