banner
李大仁博客

李大仁博客

天地虽大,但有一念向善,心存良知,虽凡夫俗子,皆可为圣贤。

[Algorithm] 使用位元運算的方法來實現無符號整數的除法原理及程式

相信知道除法的作用的人都知道除法怎麼來計算吧,不過計算機計算除法的方法可能有點浪費資源了以下是使用位計算轉換除法的過程,相信知道遊戲編程的朋友對這個應該不陌生吧

原理:假如要實現 A/B,B 如果是 2 的整數次方的話,那就不用說的,直接位移了運算如果是 0,這個就不要問我了 A/0 等於多少我也不知道。

程式碼:

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

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 步.

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。