LCR001-两数相除

求解代码

//定义移位边界，防止左移溢出privatestaticfinalintBOUND=Integer.MIN_VALUE>>1;//被除数是最小负数，除数是-1，返回最大正数publicintdivide(inta,intb){if(a==Integer.MIN_VALUE&&b==-1){returnInteger.MAX_VALUE;}if(a==0||b==1){returna;}elseif(b==-1){return-a;}intnegative=2;// 统一转为负数计算，避免MIN_VALUE取反溢出if(a>0){negative--;a=-a;}//仅处理a、b均为负数的情况，返回正的商if(b>0){negative--;b=-b;}intans=helpDivide(a,b);returnnegative==1?-ans:ans;}privateinthelpDivide(inta,intb){// 被除数绝对值 == 除数绝对值，商为1if(a==b){return1;}intres=0;intshift=getMaxShift(a,b);while(a<=b){while(a>(b<<shift)){shift--;}a-=(b<<shift);// 减去 b×2^shiftres+=(1<<shift);// 商累加 2^shift}returnres;}// 获取除数b的最大有效移位次数privateintgetMaxShift(inta,intb){intshift=0;inttmp=b;while(tmp>a&&tmp>=BOUND){tmp<<=1;shift++;}returnshift;}

小贴士

必须以除数为起点左移（倍增），而非被除数。

Integer.MIN_VALUE = -2^31取反会溢出。

两个负数相比较时，a更小表示绝对值更大。