移位实现乘法和除法——C/C++

冷不防 2023-06-19 11:19 78阅读 0赞

## 一、思想（仅实现整数） ##

**没有考虑是否超出最大值与最小值范围（MAX\_INT = 2147483647，MIN\_INT = -2147483648）**  
移位实现乘法和除法（需要用到加法和减法）。  
移位都知道是乘是左移 n 位，除是右移 n 位，就导致了乘除 2n

**都是先记录最终符号，然后转换成正数运算**

**1、乘法**  
关键是在乘数，考虑是 2 的几次方，用类似贪心算法，被乘数乘了 2 的几次方，然后乘数减去即可，直至乘数为0。

> 例如：  
> 10 \* 9  
> = 10 \* (8 + 1)  
> = 10 \* (23 \+ 20)  
> = 10 << 3 + 10 << 0  
> = 90

**2、除法**  
关键是在除数，考虑是 2 的几次方，用类似贪心算法，被除数有几个除数的 2 的几次方，然后被除数减去除数的 2 的几次方即可，直至小于除数。

> 例如：  
> 10 / 3  
> = 10 / (2 + 1)  
> = 10 / (21 \+ 20)  
> 商 = 1 << 1 + 1 << 0 = 3  
> 余 = 10 - 3 << 1 - 3 << 0 = 1

## 二、代码 ##

**1、乘法**

void MUL(int src, int dst, int* pro) {
        
    	bool sign = ((src ^ dst) < 0);			//判断符号
    	int res = 0;							//结果
    	int muled = abs(src);					//被乘数
    	int mul = abs(dst);						//乘数
    
    	for (int i = 10; i >= 0; i--) {
        			//类似贪心算法，移位求解
    		if ((1 << i) <= dst) {
        
    			res = res + muled << i;
    			mul = mul - (1 << i);
    		}
    	}
    	sign ? (*pro = -res) : (*pro = res);
    }

**2、除法**

void DIV(int src, int dst, int* quo, int* rem) {
        
    	bool sign = ((src ^ dst) < 0);			//判断符号
    	int res = 0;							//结果
    	int dived = abs(src);					//被除数
    	int div = abs(dst);						//除数
    
    	for (int i = 10; i >= 0; i--) {
        			//类似贪心算法，移位求解
    		if (dived >> i >= dst) {
        
    			res = res + (1 << i);
    			dived = dived - (div << i);
    		}
    	}
    	sign ? (*quo = -res) : (*quo = res);
    	*rem = dived;
    }

## 三、调试 ##

#include <stdio.h>
    #include <math.h>
    #include <malloc.h>
    
    void MUL(int src, int dst, int* pro) {
        
    
    }
    
    void DIV(int src, int dst, int* quo, int* rem) {
        
    
    }
    
    int main() {
        
    	int src, dst;
    	int* pro = (int*)malloc(sizeof(int));
    	int* quo = (int*)malloc(sizeof(int));
    	int* rem = (int*)malloc(sizeof(int));
    
    	printf("请输入 src: ");
    	scanf("%d", &src);
    	printf("请输入 dst: ");
    	scanf("%d", &dst);
    
    	MUL(src, dst, pro);
    	printf("积为 %d\n", *pro);
    	DIV(src, dst, quo, rem);
    	printf("商为 %d，余数为 %d\n", *quo, *rem);
    
    	return 0;
    }

## 四、结果 ##

**1、符号相同**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

**2、符号不同**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191206121507210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191206121632809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70