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

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

两数相除

https://leetcode.com/problems/divide-two-integers

题目:

分析:

除法的意义就在于：求a可以由多少个b组成。那么由此我们可得除法的实现：求a能减去多少个b，做减法的次数就是除法的商。

辅助代码:

加 键 乘

publicstaticintadd(inta,intb){intsum=a;while(b!=0){sum=a^b;b=(a&b)<<1;a=sum;}returnsum;}publicstaticintnegNum(intn){returnadd(~n,1);}publicstaticintminus(inta,intb){returnadd(a,negNum(b));}publicstaticintmulti(inta,intb){intres=0;while(b!=0){if((b&1)!=0){res=add(res,a);}a<<=1;b>>>=1;}returnres;}

除法逻辑分析

isNeg(int n) 判断一个数是否小于0

publicstaticbooleanisNeg(intn){returnn<0;}

正常相除逻辑 c= a/b

a= 2的K次方 * b + 2的(K-n)次方*b +…

最后c = b * ( 2^k + 2^(k-n)+…)

publicstaticintdiv(inta,intb){intx=isNeg(a)?negNum(a):a;inty=isNeg(b)?negNum(b):b;intres=0;for(inti=30;i>=0;i=minus(i,1)){if((x>>i)>=y){res|=(1<<i);x=minus(x,y<<i);}}returnisNeg(a)^isNeg(b)?negNum(res):res;}

1. isNeg(int n) 先全部转成正数来计算
2. int是32位,0-31,其中第31位表示符号位,一位一位的去做判断
3. (x >> i) >= y , x右移去找能大于等于y的,(等同于y左移小于等于x,不过左移,因为符号位的关系,有安全隐患) --------判断K的值是否存在
4. 找到符合条件的位数,记录下来 用res= res | (1 << i);2的k次方存在,对应位数记录为1
5. 然后x减去 y << i
6. 循环

return isNeg(a) ^ isNeg(b) ? negNum(res) : res;

a != b 可以转换为 a ^ b

怎么解决系统最小值转绝对值

最小负数 相反数 也是最小负数

分析

publicstaticintdivide(inta,intb){if(a==Integer.MIN_VALUE&&b==Integer.MIN_VALUE){return1;}elseif(b==Integer.MIN_VALUE){return0;}elseif(a==Integer.MIN_VALUE){if(b==negNum(1)){returnInteger.MAX_VALUE;}else{intc=div(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}}else{returndiv(a,b);}}

1. a 和 b都是系统最小值,则返回1
2. a不是系统最小, b是系统最小值, ,则返回0
3. a是系统最小值, b不是
4. a也不是 ,b也不是----可以直接用上述div(int a, int b)方法

a是系统最小值, b不是,分2种情况

if(b==negNum(1)){returnInteger.MAX_VALUE;}else{intc=div(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}

第一种: 如果a是系统最小值,且b等于-1

计算机底层规定: 系统最小值比系统最大值多1

比如int范围是: -128到127

1. 按道理等于系统最大值+1,
2. 因为计算机底层不存在,系统最大值+1
3. 所以按leetcode规定,返回系统最大值

所以leetcode规定: 系统最小值/-1 =系统最大值

第二种: 如果a是系统最小值,且b不等于-1

那么令a+1去除以b,后面再去补偿

两数相除----总的代码

publicclassCode03_BitAddMinusMultiDiv{publicstaticintadd(inta,intb){intsum=a;while(b!=0){sum=a^b;b=(a&b)<<1;a=sum;}returnsum;}publicstaticintnegNum(intn){returnadd(~n,1);}publicstaticintminus(inta,intb){returnadd(a,negNum(b));}publicstaticintmulti(inta,intb){intres=0;while(b!=0){if((b&1)!=0){res=add(res,a);}a<<=1;b>>>=1;}returnres;}publicstaticbooleanisNeg(intn){returnn<0;}publicstaticintdiv(inta,intb){intx=isNeg(a)?negNum(a):a;inty=isNeg(b)?negNum(b):b;intres=0;for(inti=30;i>=0;i=minus(i,1)){if((x>>i)>=y){res|=(1<<i);x=minus(x,y<<i);}}returnisNeg(a)^isNeg(b)?negNum(res):res;}publicstaticintdivide(inta,intb){if(a==Integer.MIN_VALUE&&b==Integer.MIN_VALUE){return1;}elseif(b==Integer.MIN_VALUE){return0;}elseif(a==Integer.MIN_VALUE){if(b==negNum(1)){returnInteger.MAX_VALUE;}else{intc=div(add(a,1),b);returnadd(c,div(minus(a,multi(c,b)),b));}}else{returndiv(a,b);}}}