大家好，欢迎来到IT知识分享网。

二进制乘除法原理

计算机所能完成的最基本操作是加减法和左右移。
虽然ISA中一般都有MUL类指令，但是这些经过译码之后最终的元操作还是加法和移位指令。

二进制乘法

假设不能使用乘除运算求a×b的结果，当a=b=123时，最直接的方法是通过88个88相加。但是，我们不难发现这样的规律：
123 × 123 = （100+20+3）×123 = （100×123） + （20 × 123） + （3 × 123）
因此，我们需要进行计算的次数为min(len(a), len(b))。
根据这个原理，不难想出二进制的乘法运算：
0011 * 1001 = ( 0011 * 1000)+( 0011 * 0001)
注意，这时应该使用位移运算来取代乘法运算：
0011*1000 => 3<<3
0011 * 0001 => 3<<0

//不用乘除做整数乘法运算
int Mult(int a, int b){ 
   
	int ans = 0;
	for (int i = 0; i < 32; i++){ 
   
		ans += ( b & (1 << i) ? a << i : 0);
	}
	return ans;
}

二进制除法

二进制除法的原理与在十进制时差不多，但实现起来要比二进制乘法稍微复杂一些，先上一个例子（38除以6等于6余2）：

我们从被除数的最高位开始，每步循环结束后被除数必定小于除数，然后通过位移的方式让被除数长度加1。

//二进制除法运算
int Dvi(int a, int b){ 
   
	int ans = 0;
	for (int j = 31; j >= 0; j--){ 
   
		int tmp = a >> j;
		if (tmp >= b){ 
   
			ans = ans | (1 << j);
			a -= (b << j);
		}
	}
	return ans;
}