非2次幂的除法移位实现（迟来的答案：20180330）

辛昕 · 发表于2017-12-10 22:29

非2次幂的除法移位实现（迟来的答案：20180330） [复制链接]

本帖最后由辛昕于 2018-3-30 01:56 编辑

公布我的答案——
其实这不算什么好答案，至少比不上最后一个有效回答。
但相对来说比较简单。

举个例子
要完成 a / 3；
我的思路是：
除数是没办法“分配律”的。只有被除数才可以。
所以，首先要把除数化成一个 2次幂

例如除以3

可以写成 12/4,或者 24/8 ——因为3这个数比较完整且比较简单，所以就没必要往下列举也没必要考虑什么最简单。
那就变成
a * 12 / 4
除以4是简单的，左移2位；
乘以12呢，如果不用移位，似乎就没意义了，但乘以12要实现成移位却是很简单的。

a * (8 + 4)
于是就变成 a 右移 3位加上 a 右移2 位

这个方法，其实不好
第一、不具备通用性——要针对每个被除数进行手动设置这个转换。
当除数是一个比较复杂的数或者浮点数时，你还要考虑换成多大的2次幂，才能实现足够的精度；
第二、被除数无形中增加了运算，而且由于前面提到的，换成多大的2次幂不同，被除数可能被拆分成3个2移位或者5个移位，这个时候
运算速度得不到保证，而且可能得不偿失。

总而言之，这是我在一次做一个针对一个特定的固定除数时，想到的定点优化方法。
但实际上，我发现，当我想把它推广成通式的时候。
整体速度提高不大，几乎没有意义。

对于2,4,8,16,32.......等2次幂为除数的除法，都可以直接转为右移，从而显著提高运算速度。
那么，问题来了~
如果除数是一般的3,5,6,7,非2次幂——
我们先不讨论最终的方案，是否真的提高了速度，请问，你还能把它实现成移位吗？

请给出你的方案和相应的代码（应该不会很长吧）

每个有效的不同的答案，私人赠送100芯币。

huaiqiao · 发表于2017-12-11 18:30

直接将除数写成pow(x,3). 表示3的x次幂的值，直接除啊。难道还有其他好的办法么。

辛昕 · 发表于2017-12-11 23:12

huaiqiao 发表于 2017-12-11 18:30
直接将除数写成pow(x,3). 表示3的x次幂的值，直接除啊。难道还有其他好的办法么。

不许使用库函数。
说了位移实现。
当然也允许使用加减

辛昕 · 发表于2017-12-11 23:13

当然，即使我只允许你使用位移和位运算也是可以的

huaiqiao · 发表于2017-12-12 10:00

辛昕发表于 2017-12-11 23:12
不许使用库函数。
说了位移实现。
当然也允许使用加减

为啥不能用？
想不通。。。。。

我前面没有好好看你帖子，我以为库函数都能实现的，你还发帖子。觉得好奇怪。

你说位移。我才看到这个点。

辛昕 · 发表于2017-12-12 10:01

huaiqiao 发表于 2017-12-12 10:00
为啥不能用？
想不通。。。。。

我前面没有好好看你帖子，我以为库函数都能实现的，你还发帖子。觉得 ...

wsdymg · 发表于2017-12-12 10:55

计算机上乘和除都可以用移位和加减来实现，方法就是：
一，先把被除数放到一个寄存器中，比如，al中，再把ah赋0即被除数为ax
二，ax左移一位，将ah减去除数，结果为负用加法恢复上面的内容

辛昕 · 发表于2017-12-12 14:38

wsdymg 发表于 2017-12-12 10:55
计算机上乘和除都可以用移位和加减来实现，方法就是：
一，先把被除数放到一个寄存器中，比如，al中，再 ...

不懂，希望能转换成与汇编无关的，比较通用的方法。

wsdymg · 发表于2017-12-14 09:34

辛昕发表于 2017-12-12 14:38
不懂，希望能转换成与汇编无关的，比较通用的方法。

找了下资料介绍：

x/y其实就是，x不断减y的过程。小学时候学的长长除法就是这个原理。
用二进制的除法x/y，比十进制容易写，商不是0即是1，而且如果除数大于除数的1倍，商就是标记在另一个位上面了

二进制除法x/y=0.1001/0.1011手工计算如下
         0.11
   _______
0.1001/0.1001
      10010(后面补0)
      -1011
   ------
      111(余数)
      1110(后面补0)
      -1011
   --------
         1(余数)

设ri表示第i次运算后所得的余数,则：
若ri>0，则商1，余数和商左移1位，再减去除数，即ri+1=2ri-y
若ri<0，则商0，余数和商左移1位，再加上除数，即ri+1=2ri+y

用85/6来举例,85/6=1010101/110
a.101(0101)左移1位到第3位都小于110，因此商=000
b.1010(101)左移四位是1010,比110大，商=0001,余数=1010-110=100(101)
c.余数100(101)左移一位是1001,比110大，商=00011,余数=1001-110=11(01)
d.余数11(01)左移一位是110,等于110，商=000111,余数=0(1)
e.余数0(1)左移一位是01,小于110,商=0001110,余数=01

因此85/6=1010101/110=0001110，即14，余数为最后的余数1