初级--05--- 取模运算转化为位运算、位运算进行加减乘除
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 取模运算 转化为 位运算
- 公式:
- ==a%b = a&(b-1) ，且b=1<<k（k为整数）==
- 案例:
- num % 64 等于 num & 63
- 原理:
- 注意:
- 取模的数b, 要满足b为2的整数次幂（即b=1<<k，k为整数）,公式转化才成立
- 位运算进行加减乘除
- 初级--01---二进制、位运算
- num >> 6 相当于 num/64
- 1. 加法：add
- 无进位信息和+进位信息和 = 加法的和
- ==a^b + (a&b)<<1==
- 2. 减法: minus
- 可以将减法转换成加法计算。a - b = a + (-b)
- 相反数
- 正数相反数 = 其反码+1
- 减法代码
- 3. 乘法: multi
- 4. 除法: divide
- 位运算--01---两数相除
取模运算 转化为 位运算
公式:
若满足b为2的整数次幂（即b=1<<k，k为整数）时，可用一个特殊的小技巧将取模运算转化为位运算，
a%b = a&(b-1) ，且b=1<<k（k为整数）
案例:
num % 64 等于 num & 63
原理:
注意:
取模的数b, 要满足b为2的整数次幂（即b=1<<k，k为整数）,公式转化才成立
位运算进行加减乘除
初级–01—二进制、位运算
num >> 6 相当于 num/64
1. 加法：add
- 由a^b可得按位相加后没有进位的和；
- 由a&b可得可以产生进位的地方；
- 由(a&b)<<1得到进位后的值。
- 那么 按位相加后原位和+进位和 就是加法的和了，而 a^b + (a&b)<<1 相当于把 +
两边再代入上述三步进行加法计算。直到进位和为0说明没有进位了则此时原位和即所求和。
无进位信息和+进位信息和 = 加法的和
a^b + (a&b)<<1
publicstaticintadd(inta,intb){intsum=a;while(b!=0){sum=a^b;//无进位信息和b=(a&b)<<1;//进位信息和a=sum;//无进位相加信息}returnsum;}2. 减法: minus
可以将减法转换成加法计算。a - b = a + (-b)
相反数
正数相反数 = 其反码+1
publicstaticintnegNum(intn){returnadd(~n,1);}减法代码
publicstaticintnegNum(intn){returnadd(~n,1);}publicstaticintminus(inta,intb){returnadd(a,negNum(b));}3. 乘法: multi
publicstaticintmulti(inta,intb){intres=0;while(b!=0){if((b&1)!=0){res=add(res,a);}a<<=1;b>>>=1;}returnres;}4. 除法: divide
除法的意义就在于：求a可以由多少个b组成。那么由此我们可得除法的实现：求a能减去多少个b，做减法的次数就是除法的商。
位运算–01—两数相除
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);}}