李大仁博客

I believe that those who know the purpose of division also know how to calculate division. However, the method of calculating division in computers may waste some resources. The following is the process of converting division using bitwise calculations. I believe that friends who know game programming should be familiar with this.

Principle: If A/B needs to be implemented, if B is a power of 2, then it is straightforward to perform bitwise shift operations. If B is 0, don't ask me what A/0 equals, because I don't know either.

Code:

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 is an important number, suitable for 32-bit machine operations
float f = 2 ^ r / B;
float t = f - ( int ) f; //Get the decimal part
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);
}

Explanation:
First, obtain the highest bit of B, which is max(log2^B).
Then, add 32 to this b. 32 is an important number, suitable for 32-bit machine operations.
Assume r = 32 + b.
Calculate f = 2^r / B.
Get the decimal part t of f.
If t < 0.5, the result is (((A+1) * f) >> r)-(A>>count).
If t > 0.5, the result is ((A*f) >> r)-(A>>count).
If t = 0.5, error.

Attachment: Assembly source code for machine implementation of integer division, from CSDN

mov     cx,16   ;The result is 16 bits, loop 16 times

start:
SHL AX , 1 ;Shift the dividend left by 1 bit
RCL DX , 1
CMP DX , BX ;Try to divide
JB next ;The current quotient is 0, do not process
SUB DX , BX ;Subtract the divisor
OR AX , 1
next: loop start ;Loop

Basic idea: We can recall the manual calculation process of division by stages:

1. Try to divide: Align the dividend and divisor, and see how many times the dividend is greater than or equal to the divisor, obtaining the current quotient. Since it is a decimal number, the current quotient is 0-9.
2. Subtract the current quotient times the divisor from the dividend.
3. Shift the dividend left by 1 bit, go to the first step, and continue to try to divide.

Then, let's look at binary division, which is similar to manual decimal division. Binary division also requires 3 steps, but it is simpler.

1. Try to divide: Since it is a binary number, the current quotient is 0-1. If the dividend is greater than the divisor, set the current quotient to 1; otherwise, set it to 0.
2. Subtract the current quotient times the divisor from the dividend. If the current quotient is 1, subtract the divisor; otherwise, the dividend remains unchanged.
3. Shift the dividend left by 1 bit (binary shift), go to the first step.