位运算--01---两数相除

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录两数相除题目:分析:辅助代码:加 键 乘除法逻辑分析isNeg(int n) 判断一个数是否小于0正常相除逻辑 c a/ba 2的K次方 * b 2的(K-n)次方*b .....最后c b * ( 2^k 2^(k-n)....)return isNeg(a) ^ isNeg(b) ? negNum(res) : res;a ! b 可以转换为 a ^ b怎么解决系统最小值转绝对值最小负数 相反数 也是最小负数分析a是系统最小值, b不是,分2种情况第一种: 如果a是系统最小值,且b等于-1计算机底层规定: 系统最小值比系统最大值多1比如int范围是: -128到127所以leetcode规定: 系统最小值/-1 系统最大值第二种: 如果a是系统最小值,且b不等于-1那么令a1去除以b,后面再去补偿两数相除----总的代码两数相除https://leetcode.com/problems/divide-two-integers题目:分析:除法的意义就在于求a可以由多少个b组成。那么由此我们可得除法的实现求a能减去多少个b做减法的次数就是除法的商。辅助代码:加 键 乘publicstaticintadd(inta,intb){intsuma;while(b!0){suma^b;b(ab)1;asum;}returnsum;}publicstaticintnegNum(intn){returnadd(~n,1);}publicstaticintminus(inta,intb){returnadd(a,negNum(b));}publicstaticintmulti(inta,intb){intres0;while(b!0){if((b1)!0){resadd(res,a);}a1;b1;}returnres;}除法逻辑分析isNeg(int n) 判断一个数是否小于0publicstaticbooleanisNeg(intn){returnn0;}正常相除逻辑 c a/ba 2的K次方 * b 2的(K-n)次方*b …最后c b * ( 2^k 2^(k-n)…)publicstaticintdiv(inta,intb){intxisNeg(a)?negNum(a):a;intyisNeg(b)?negNum(b):b;intres0;for(inti30;i0;iminus(i,1)){if((xi)y){res|(1i);xminus(x,yi);}}returnisNeg(a)^isNeg(b)?negNum(res):res;}isNeg(int n) 先全部转成正数来计算int是32位,0-31,其中第31位表示符号位,一位一位的去做判断(x i) y , x右移去找能大于等于y的,(等同于y左移小于等于x,不过左移,因为符号位的关系,有安全隐患) --------判断K的值是否存在找到符合条件的位数,记录下来 用res res | (1 i);2的k次方存在,对应位数记录为1然后x减去 y i循环return isNeg(a) ^ isNeg(b) ? negNum(res) : res;a ! b 可以转换为 a ^ b怎么解决系统最小值转绝对值最小负数 相反数 也是最小负数分析publicstaticintdivide(inta,intb){if(aInteger.MIN_VALUEbInteger.MIN_VALUE){return1;}elseif(bInteger.MIN_VALUE){return0;}elseif(aInteger.MIN_VALUE){if(bnegNum(1)){returnInteger.MAX_VALUE;}else{intcdiv(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}}else{returndiv(a,b);}}a 和 b都是系统最小值,则返回1a不是系统最小, b是系统最小值, ,则返回0a是系统最小值, b不是a也不是 ,b也不是----可以直接用上述div(int a, int b)方法a是系统最小值, b不是,分2种情况if(bnegNum(1)){returnInteger.MAX_VALUE;}else{intcdiv(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}第一种: 如果a是系统最小值,且b等于-1计算机底层规定: 系统最小值比系统最大值多1比如int范围是: -128到127按道理等于系统最大值1,因为计算机底层不存在,系统最大值1所以按leetcode规定,返回系统最大值所以leetcode规定: 系统最小值/-1 系统最大值第二种: 如果a是系统最小值,且b不等于-1那么令a1去除以b,后面再去补偿两数相除----总的代码publicclassCode03_BitAddMinusMultiDiv{publicstaticintadd(inta,intb){intsuma;while(b!0){suma^b;b(ab)1;asum;}returnsum;}publicstaticintnegNum(intn){returnadd(~n,1);}publicstaticintminus(inta,intb){returnadd(a,negNum(b));}publicstaticintmulti(inta,intb){intres0;while(b!0){if((b1)!0){resadd(res,a);}a1;b1;}returnres;}publicstaticbooleanisNeg(intn){returnn0;}publicstaticintdiv(inta,intb){intxisNeg(a)?negNum(a):a;intyisNeg(b)?negNum(b):b;intres0;for(inti30;i0;iminus(i,1)){if((xi)y){res|(1i);xminus(x,yi);}}returnisNeg(a)^isNeg(b)?negNum(res):res;}publicstaticintdivide(inta,intb){if(aInteger.MIN_VALUEbInteger.MIN_VALUE){return1;}elseif(bInteger.MIN_VALUE){return0;}elseif(aInteger.MIN_VALUE){if(bnegNum(1)){returnInteger.MAX_VALUE;}else{intcdiv(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}}else{returndiv(a,b);}}}