Home > 算法研究 > [算法]用位运算的方法实现无符号整数的除法原理及程序

[算法]用位运算的方法实现无符号整数的除法原理及程序

相信知道除法的作用的人都知道除法怎么来计算吧,不过计算机计算除法的方法可能优点浪费资源了以下是使用位计算转换除法的过程,相信知道游戏编程的朋友对这个应该不陌生吧

原理:假如要实现A/B,B如果是2的整数次方的话,那就不用说的,直接位移了运算如果是0,这个就不要问我了A/0等于多少我也不知道。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bitDivide(){
if(B==0) error(0);//B=0
while(B >> 1){
  int count;
 count ++;
 if (B==0)  output(A >> count) ;//Log2^B=0
}
int r = count + 32; //32这个数字很重要,适合32位机器运算
float f =  2 ^ r / B;
float t = f - ( int ) f; //取小数部分
float result;
if(t>0.5)
   result=(A * f >>  r) - (A >> count);
else if(t<0.5)
  result=(( A + 1 ) * f >> r)-(A >> count);
else  error(0);
output(result);
}

解释
首先取得B最高位就是 max(log2^B)
然后让这个b加上 32 ,32这个数字很重要,适合32位机器运算
假设一个 r = 32 + b
再计算 f = 2^r / B,
再取 f的小数部分t
t < 0.5 , 结果为 (((A+1) * f) >> r)-(A>>count)
t > 0.5 , 结果为 ((A*f) >> r)-(A>>count)
t = 0.5, 错误

附:机器实现整数除法的汇编源程序,来自CSDN

1
2
3
4
5
6
7
8
9
    mov     cx,16   ;结果为16位,循环16次
start:
SHL  AX , 1     ;被除数左移1位
RCL  DX , 1
CMP DX , BX   ;试商
JB  next         ;当前商为0,不处理
SUB DX , BX   ;减去阶数
OR AX , 1
next:  loop  start ;循环

基本思想: 我们可以回想阶法的手算运程:
1。试商:将被除数和除数左对齐,看看被除大于等于除数的几倍,得到当前商,因为是十进制数,故当前商为0-9.
2. 将被除数减去除数的当前商?倍.
3. 被除数左移1位,转第一步,继续试商。

然后 看二进制除法,和十进制除法手算类类似,二进制除法也需3步,不过更加简单。
1. 试商,因为是二进制数,故 当前商 为0-1. 被除数大于除数,当前商 置1,小于除数,当前商 置0
2。被除数 减去 除数的 当前商 倍。当前商为1,被除数减去除数。否则,被除数不变。
3. 被除数 左移1位(二进制的移位),继续 第1步.

Categories: 算法研究 Tags: ,
  1. No comments yet.
  1. No trackbacks yet.