力扣题目整数除法

发布时间 2023-04-05 21:52:34作者: 针眼画师

在力扣上做题,这个题涉及到的整数溢出问题十分恼人,主要也是我不熟悉这些东西,做的很艰难,下面是题目:

给定两个整数 a 和 b ,求它们的除法的商 a/b ,要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意:

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231−1]。本题中,如果除法结果溢出,则返回 231 − 1

我最后写出了如下代码:

#include <stdio.h>
#define ABS(i) (( i < 0 ) ? ( -i ) : ( i ))   // 定义一个取绝对值函数
// 本程序是之前程序的加速算法 
int main()
{
	const int MAX = 2147483647;
	const int MIN = -2147483648;
    
	int a=0,b=0;
	int b1=0; 
	int sign=0;  // 记录是否异号,1是,0否 
	int ans=0;
	
	scanf("%d,%d",&a,&b);
	// 用于滚动加速计算的b值,用b1表示 
	printf("a=%d,b=%d\n",a,b);
	// 对两个数是否负号进行判断和记录 
	if (a<0||b<0) 
	{
        sign=1;
        if (a<0&&b<0) sign=0;             
	}
	//  判断是否在int的范围内 
	if ((a<=MAX)&&(b<=MAX)&&(a>MIN)&&(b>MIN)&&b!=1)
	{
		// 要求a>b,这样值才能大于1,因此取绝对值 
		if (ABS(a)>=ABS(b)&&b!=0)
		{
			// 计算部分 
			// 这里a,b的值可以直接取绝对值了,没有问题
			a=ABS(a);
			b=ABS(b);
			b1=-b; 
			// a>b就继续减,直到减不下去,ans 就是a/b得到的那个整数了 
			// 这里是一种滚动加速,我自己取的名字 ;这里一般算不干净,a还会剩,因此还需要下面再用b算一遍。 
			// 这里也用负号,防止溢出 
			while (-a<=b1)
			{
				// 保护一下,防止b的值很大,走不过第一次循环就溢出 
				if (b1<1073741824) break;
				a=a+b1;
				b1=b1+b1;
				ans=ans+ans+1;
				printf("%d\n",ans);
			}
			// 这里清理残余,大头在上一部分已经计算了 ,因此速度会得到提升 
			while (a>=b)
			{
				a=a-b;
				ans++;
				printf("%d\n",ans);
			}
			// 根据对正负号的记录更改正负号 
			if (sign==1)
			{
				ans=-ans;
			}
		}
		else
		{
			ans=0;
		}
	}
	else if (b==1)
	{
		ans=a;
	}
	// 添加b= -2147483648情况,防止在上面取绝对值之后溢出 
	else if (b==MIN)
	{
		// 考虑周全 
		if (a!=MIN) 
		{
			ans=0;
		}
		else
		{
			ans=1;
		}
	}
	// a==-2147483648时无法取正,因为正数最大只有 2147483647,所以要单独处理,保持它的负号,用加法即可 
	else if (a==MIN)
	{
		// 这里也改为加速算法,为了防止出现 1073741824导致的溢出错误,给一个负号,就不会溢出了 
		b1=-ABS(b); 
		// 这里要求与a比较的值是负数,所以才给绝对值加负号 
		while (a<=b1)
		{
			// 保护一下,防止b的值很大
			if (b1<1073741824) break;
			a=a-b1;
			b1=b1+b1;
			ans=ans+ans+1;
			printf("%d\n",ans);
		}
		while (a<=-ABS(b))
		{
			// 这个判断放在前边,以防止溢出 
			if (ans==MAX)
			{
				break;
			}
			a=a+ABS(b);
			ans++;
			printf("%d\n",ans);
		}
		// 符号修正 
		if (sign==1)
		{
			ans=-ans;
		}
	} 
	printf("ans=%d\n",ans);
	return 0;
} 

这是我在本地以main函数写的
我一共提交了18次,第18次才算合格,导致次数很多的原因是代码的考虑不够全面,提交之后因为有大量的数据去检验,总是这里没考虑到,或者那里漏掉,然后我再修补。
我现在来看,我缺失的能力不只是在代码上,在写代码之前,对整个代码的设计没有做好,这是需要尽快补好的。