【剑指|【剑指 Offer II 001. 整数除法】同leedcode 29.两数相除【剑指OfferII001.整数除法】同

剑指 Offer II 001. 整数除法
文章图片

文章图片

解题思路

在计算的时候将负数转化为正数，对于32位整数而言，最小的正数是-2^31, 将其转化为正数是2^31，导致溢出。因此将正数转化为负数不会导致溢出。
设置一个变量，用来记录正数个数，以便在最后的结果调整正负号。
特殊情况，可能溢出的情况讨论，由于是整数除法，除数不为0，商的值一定小于等于被除数的绝对值，因此，int型溢出只有一种情况，(-2^31)/(-1) = 2^31。

【【剑指|【剑指 Offer II 001. 整数除法】同leedcode 29.两数相除】最容易想到的是通过减法代替除法，但是会超时

class Solution { public int divide(int a, int b) { if(a == 0)return 0; int symbolNum = (a>0)^(b>0)? -1:1 ; //可以对下面的代码段进行优化 /* int symbolNum = 1; if(a>0&&b>0 || a<0&&b<0) symbolNum = 1; else{ symbolNum = -1; }*/if(a==Integer.MIN_VALUE && b==-1) return Integer.MAX_VALUE; if(a>0)a = -a; if(b>0)b = -b; int ans = 0; while(a <= b){ a -= b; ans++; } return symbolNum == -1? -ans:ans; } }

优化思路不使用减法那种被除数对除数一次一次减的形式（在被除数过大而除数很小的情况下会超时），而是试图减2个、4个、8个....找到最大的2的n次方。将被除数减去除数的2的n次方倍，然后将剩余的被除数重复前面的步骤。
例如：
为了求得15/2的商，先从15里减去8 (23)，得到7；再从7里减去4(22),得到3；再从3里减去2(2^1),得到1，此时1小于2，因此商是3+2+1=7。
在计算两个负数的除法时，防止每次计算除数的2倍，会导致大数溢出，要保证计算2倍之后的数大于(-231)/2。如果时计算两个正数的除法，要保证计算2倍之后的数小于(231-1)/2。

class Solution { public int divide(int a, int b) { //int 型整数的除法只有一种情况会导致溢出，即（-2^31）/(-1) if(a==Integer.MIN_VALUE && b==-1) return Integer.MAX_VALUE; if(a == 0 || b == 1)return a; else if(b == -1) return -a; int symbolNum = (a>0)^(b>0)? -1:1 ; // 由于（-2^31）转换为正数会溢出，但是任意正数转换为负数都不会溢出 // 故，记录负数的个数，并将正数转换为负数方便统一计算 if(a>0)a = -a; if(b>0)b = -b; // while(a <= b){//这样写确实可以过案例，但是会超时 //a -= b; //ans++; // } if(a == b)return symbolNum == -1? -1:1; int ans = 0; while(a<=b){//小于是因为现在a,b都是负数 int value = https://www.it610.com/article/b; //统计最多有几个减数（2的n次方个） int tmpQuotient = 1; while(value + value> Integer.MIN_VALUE && value + value >= a){//减到不够了为止 value += value; tmpQuotient += tmpQuotient; } ans +=tmpQuotient; a -= value; }return symbolNum == -1? -ans:ans; }}

但上述代码只通过了700+样例，找了半天发现是value + value > Integer.MIN_VALUE这里出问题了，要改成value >0xc0000000。（0xc0000000是Integer.MIN_VALUE的一半）
完整代码贴在这儿

class Solution { public int divide(int a, int b) { //int 型整数的除法只有一种情况会导致溢出，即（-2^31）/(-1) if(a==Integer.MIN_VALUE && b==-1) return Integer.MAX_VALUE; if(a == 0 || b == 1)return a; else if(b == -1) return -a; int symbolNum = (a>0)^(b>0)? -1:1 ; // 由于（-2^31）转换为正数会溢出，但是任意正数转换为负数都不会溢出 // 故，记录负数的个数，并将正数转换为负数方便统一计算 if(a>0)a = -a; if(b>0)b = -b; // while(a <= b){//这样写确实可以过案例，但是会超时 //a -= b; //ans++; // } if(a == b)return symbolNum == -1? -1:1; int ans = 0; while(a<=b){//小于是因为现在a,b都是负数 int value = https://www.it610.com/article/b; //统计最多有几个减数（2的n次方个） int tmpQuotient = 1; while(value>0xc0000000 && value + value >= a){//减到不够了为止 value += value; tmpQuotient += tmpQuotient; } ans +=tmpQuotient; a -= value; }return symbolNum == -1? -ans:ans; }}

这里补充一下int 类型数据的最大值，最小值及其十六进制表示方式：
在int类型（32位）中：
正整数的最大值为 0x7fffffff 也就是十进制的 2147483647
正整数的最小值为 0x00000001 也就是十进制的 1
0表示为：0x00000000
负整数的最大值为 0xffffffff 也就是十进制的 -1
负整数的最小值为 0x80000000 也就是十进制的 -2147483648