c++ 使用超过8步的位运算符实现更精确的除法[已关闭]

lnlaulya  于 2023-01-06  发布在  其他
关注(0)|答案(1)|浏览(141)
    • 已关闭**。此问题需要超过focused。当前不接受答案。
    • 想要改进此问题吗?**更新此问题,使其仅关注editing this post的一个问题。

9小时前关门了。
Improve this question
用更具体的数字而不是2的幂来划分uint8的最有效方法是什么?不需要像普通除法那样精确,例如:正常比特移位除法选项-2、4、8、16、32、64、128、256概念1 - 2、4、6、8、10、12、14、16 ...概念2 - 2、3、4、6、8、12、16、24、32、48、64、96、128、192、256、384
这里的目标是使函数非常高效,并且与常规的位移位除法相比,除法步骤数至少为2倍。概念1和2在这里表明,除法值是否为指数无关紧要。如果需要,可以允许一些加法或减法。

0pizxfdo

0pizxfdo1#

如果您感兴趣的是位移位除以预定义的数字,第一步是用二进制表示它的倒数,然后按相应的量进行位移位。例如,在8位算术中使用位移位除以42,如下所示:

1/42 = 0.00000110 (...)
x / 42 = (x >> 6) + (x >> 7) 
# 252 / 42 = (0b11111100 >> 6) + (0b11111100 >> 7) = 
#          = (0b00000011 + 0b00000001) = 0b00000100 = 4

正如您所看到的,精度受到所取有效位数的限制。2的幂有一个很好的特性,即在2进制和10进制中都有有限的逆。将“好看”的10进制数(如1/5)取反很容易在2进制中变成一场灾难。但是,如果“初始”2次幂除法等于使用这个列表进行移位和加法(每个移位1次,不需要加法,没有什么能比得上这里的性能):

0b0.00000001 = 1/256
0b0.00000010 = 1/128
0b0.00000100 = 1/64
0b0.00001000 = 1/32
0b0.00010000 = 1/16
0b0.00100000 = 1/8
0b0.01000000 = 1/4
0b0.10000000 = 1/2

你可以简单地扩展它,例如这个列表(2位移位和1次加法):

0b0.00000011 = 1/85.(3)
0b0.00000110 = 1/42.(6)
0b0.00001100 = 1/21.(3)
0b0.00011000 = 1/10.(6)
0b0.00110000 = 1/5.(3)
0b0.01100000 = 1/2.(6)
0b0.11000000 = 1/1.(3)

当然,最佳化的程度取决于所需的移位和加法的数量,所以在这种方法中选择0b0.11111110是一个相当糟糕的主意。0b0.101 = 0.625 = 1/1.6及其右移位(0b0.01010b0.00101等)在base-10和base-2中都很好用,当然,在二进制表示中仍然只有两个1。

相关问题